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?