2
$\begingroup$

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:

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?

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me. $\endgroup$ – user93381 Sep 3 '18 at 19:30
  • $\begingroup$ No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only. $\endgroup$ – Navjot Waraich Sep 3 '18 at 20:30
  • $\begingroup$ Just for clarification, having best- and worst-case time complexity of $O(n)$ does not imply the overall complexity is $\Theta(n)$. See this. $\endgroup$ – Bruno Ely Dec 16 '18 at 0:00
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from? $\endgroup$ – user93381 Sep 3 '18 at 19:18
  • $\begingroup$ A call POSTORDER(v) can only come from a parent node p. The parent node is at depth $n$, therefore via induction we know that p only gets visited once. Therefore so does v. $\endgroup$ – Jakube Sep 3 '18 at 19:29
  • $\begingroup$ The $\Theta(1)$ stuff is the if and visit operation. They take constant time. $\endgroup$ – Jakube Sep 3 '18 at 19:30
  • $\begingroup$ I actually forgot the POSTORDER(null) calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity. $\endgroup$ – Jakube Sep 3 '18 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy