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$

2 Answers 2

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$
2
  • 2
    $\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, 2018 at 19: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$
    – sleighty
    Dec 16, 2018 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$
4
  • $\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, 2018 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, 2018 at 19:29
  • $\begingroup$ The $\Theta(1)$ stuff is the if and visit operation. They take constant time. $\endgroup$
    – Jakube
    Sep 3, 2018 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, 2018 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.