Postorder Tree Traversal Without Recursion in C++
Postorder Tree Travesal Without Recursion
There are three types of traversals in trees:Preorder,Inorder and Postorder. The traversals can be performed using recursion or stack.In this article, postorder traversal is performed using two stacks. The Last In First Out principle of stack is used to get postorder sequence.
More About Postorder Traversal:
- Postorder traversal is a depth first algorithm.
- In postorder traversal, we first move to the left subtree then to the right subtree and finally print the node.
- Post order traversal is used when we want to free the nodes of the tree.
- It is also used to find the postfix expression.
- Create two stacks: s1 and s2.
- Push the root in s1.
- Continue until s1 is empty.
- Pop the top element of s1 and push it into s2.
- Push the left and the right child of top element to s1.
- Print the s2 stack when s1 is empty.
40 50 20 30 10
Time Complexity Of Postorder Traversal without Recursion