*ROOT* LEFT RIGHT - 911 WeKnow

Types of Binary Tree traversal and its Conversion of inorder to preorder-postorder

Image for post Binary Tree Traversals

Motivation:

Pre-order traversal while duplicating nodes and values can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly.
In-order traversal is very commonly used in binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).
Post-order traversal while deleting or freeing nodes and values can delete or free an entire binary tree. It can also generate a postfix representation of a binary tree

we are using stack 🙂 So here we go!

Inorder Traversal :

LEFT ROOT RIGHT

Since we are not using recursion, we will use the Stack to store the traversal, we need to remember that inorder traversal is, first traverse the left node then root followed by the right node.

Psuedo code:

Create a Stack
Push the Root onto Stack until set the root = root.left continue till it hits the NULL.
If root is null and Stack is empty Then return, we are done.
Else Pop the top Node from the Stack and set it as, root = popped_Node.
print the root and go right, root = root.right.
Go to step. End If

Image for post working Inorder Stack

we have to keep track of the root that?s why we use stack! if we consider each subtree as separate ones it gets easier to understand the traversal and then move to stack

Inorder Traversal using stack

Output: inorder

4 2 5 1 34 2 5 1 3

Preorder Traversal: we need to remember that preorder traversal is, the first traverse the root node then left node followed by the right node.

Image for post Preorder Traversal

Output:

1 2 4 5 3 6 71 2 4 5 3 6 7

Postorder Traversal: we need to remember that preorder traversal is, the first traverse the root node then left node followed by the right node.

LEFT RIGHT ROOT

Approach:

We have seen how we do inorder and preorder traversals without recursion using Stack, But post order traversal will be different and slightly more complex than other two. Reason is post order is non-tail recursive ( The statements execute after the recursive call).
If you just observe here, postorder traversal is just reverse of preorder traversal (1 3 7 6 2 5 4 if we traverse the right node first and then left node.)
So idea is follow the same technique as preorder traversal and instead of printing it push it to the another Stack so that they will come out in reverse order (LIFO).
At the end just pop all the items from the second Stack and print it.

Image for post PostOrder Stackpreorder stack