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?