Proving Postorder Traversal's Time Complexity

Question

I am looking at the following algorithm for performing a Postorder Traversal of a binary tree

POSTORDER(root):
if root != nullthen
    POSTORDER(root.left);
    POSTORDER(root.right);
    visit root;
end if;

I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.

I have looked at the following sources:

• https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
• https://en.wikipedia.org/wiki/Reverse_Polish_notation
• https://en.wikipedia.org/wiki/Tree_traversal
• https://leetcode.com/articles/introduction-to-n-ary-trees/

I understand WHAT PostOrder traversal does, and I understand WHAT a binary tree is, but I don't know how I can prove that time complexity.

Could anybody help me on this?

Answer 1

In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.

In postorder traversal each node in binary tree is visited:

a) 1 time if it is a leaf node.

b) 1 time if it is a node with only one child (either left or right)

c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.

So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:

Best case time : $O(n)$

Worst case time : $O(n)$

Hence, we can say algorithm is $Θ(n)$.

Answer 2

Show that POSTORDER(v) will at most be called exactly once for each vertex v.

This can be done via Induction by depth:

• First show that POSTORDER(root) will only be called once (depth 0). This is easy, since there doesn't exist a parent of root, therefore there exists no node v with v.left == root or v.right == root.
• Then assume that POSTORDER(v) will be called exactly once for every node at depth $n$, and show that this is also true for every vertex at depth $n + 1$. This should be straightforward to prove.

Since, other than the recursive calls (which we already understand), we do only constant stuff in a call of POSTORDER(v), the time complexity is $\Theta(n) \cdot \Theta(1) = \Theta(n)$.