Last Updated: 16 Dec, 2020

Tree Traversals

Easy

Asked in companies

Solve now

Problem statement

You have been given a Binary Tree of 'N'

nodes, where the nodes have integer values.

Your task is to return the ln-Order, Pre-Order, and Post-Order traversals of the given binary tree.

For example :

For the given binary tree:

Binary - Tree1

The Inorder traversal will be [5, 3, 2, 1, 7, 4, 6].
The Preorder traversal will be [1, 3, 5, 2, 4, 7, 6].
The Postorder traversal will be [5, 2, 3, 7, 6, 4, 1].

Input Format :

The first line contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

Example :

The input for the tree is depicted in the below image:

BT - 2

1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 3
Right child of 1 = 8

Level 3 :
Left child of 3 = 5
Right child of 3 = 2
Left child of 8 =7
Right child of 8 =  null (-1)


Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 2 = null (-1)
Right child of 2 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)

1
3 8
5 2 7 -1
-1 -1 -1 -1 -1 -1

Note :

1. The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

2. The input ends when all nodes at the last level are null(-1).

3. The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Output Format :

The first line of output contains 'N' single space-separated integers denoting the node's values in In-Order traversal.

The second line of output contains 'N' single space-separated integers denoting the node's values in Pre-Order traversal.

The third line of output contains 'N' single space-separated integers denoting the node's values in Post-Order traversal.

Note :

You don't need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The idea here is to use recursion for ln-Order, Pre-Order, and Post-Order traversal of a binary tree.

Steps :

Inorder traversal :

void inOrder(‘NODE’):

Visit the left subtree of ‘NODE’ i.e., call inOrder(‘NODE’ -> left).
Visit node and if ‘NODE’ != NULL then add data of node to answer.
Visit the right subtree of ‘NODE’ i.e, call inOrder(‘NODE’ -> right).

Preorder traversal :

void preOrder(‘NODE’):

Visit node and if ‘NODE’ != NULL then add data of node to answer.
Visit the left subtree of ‘NODE’ i.e., call preOrder(‘NODE’ -> left).
Visit the right subtree of ‘NODE’ i.e., call preOrder(‘NODE’ -> right).

Postorder traversal :

void postOrder(‘NODE’):

Visit the left subtree of ‘NODE’ i.e., call postOrder(‘NODE’->left).
Visit the right subtree of node i.e., call postOrder(‘NODE’->right).
Visit node and if ‘NODE’ != NULL then add data of node to answer.

Solve now

02 Approach

The idea here is to use a stack for ln-Order, Pre-Order, and Post-Order traversal of a binary tree.

Steps :

Inorder traversal :

Create an empty stack and initialize the current node as root.
Run a loop until ‘CURRENT’ != NULL or stack is not empty:
1. Push current node to stack and do ‘CURRENT’ = ‘CURRENT’ -> left until ‘CURRENT’ != NULL.
2. Then pop the top node from the stack and add data from the popped node to answer.
3. Then do ‘CURRENT’ = popped node -> right and go to step 2

Preorder traversal :

Create an empty stack and push root to stack.
Run a loop until the stack is not empty and do :
1. Pop node from the stack and add data of popped node to answer.
2. Push right child and then left child of the node to stack respectively.

Postorder traversal :

Create an empty stack and answer list.
Initialize the current node as root, and push the current node to stack.
Run a loop until the stack is not empty and do :
1. Pop-top node from the stack and set the popped node as the current node.
2. Add data of the current node to the answer list.
3. Push the left child of the current node to stack.
4. Push the right child of the current node to stack.
At last reverse all elements of the answer list.

Solve now

03 Approach

The idea here is to use Morris traversal for Inorder, Preorder, and Postorder traversal of the tree. The idea of Morris's traversal is based on the Threaded Binary Tree. In this traversal, we will create links to the predecessor back to the current node so that we can trace it back to the top of a binary tree. Here we don’t need to find a predecessor for every node, we will be finding a predecessor of nodes with only valid left child.

So Finding a predecessor will take O(N) as time as we will be visiting every edge at most two times and there are only N-1 edges in a binary tree. Here N is the total number of nodes in a binary tree.

For more details, please check the Threaded binary tree and Explanation of Morris Method

Steps :

Inorder traversal :

Create a new node, say ‘CURRENT’, and initialize it as ‘ROOT’.
Run a loop until ‘CURRENT’ !=NULL and do:
1. If ‘CURRENT’ -> left = NULL then add data of current to answer and do ‘CURRENT’ = ‘CURRENT’ ->right
2. Else In current’s left subtree, make ‘CURRENT’ as of the right child of rightmost node and visit this left child i.e. ‘CURRENT’ = ‘CURRENT’ ->left.

Preorder traversal :

Create a new node, say ‘CURRENT’, and initialize it as ‘ROOT’.
Run a loop until ‘CURRENT’!=NULL and do:
1. If the left child of ‘CURRENT’ is NULL then add ‘CURRENT’ node data to answer and do ‘CURRENT’ = ‘CURRENT’ ->right.
2. Else make a right child of inorder predecessor point to the ‘CURRENT’ node, then the following two cases will occur:
  1. If the right child of inorder predecessor points to the ‘CURRENT’ node then do right child = NULL and visit the right child of the current node i.e., ‘CURRENT’ = ‘CURRENT’ -> right.
  2. If the right child is NULL then set it to the current node. Add data of current node to answer and move to left child of the current node i.e., ‘CURRENT’ = ‘CURRENT’ -> left.

Postorder traversal :

1. The basic idea is that postorder traversal can be considered as the reverse process of preorder traversal.

2. Hence we just need to change left child to right child and always insert data of node at beginning of our answer. We can achieve this by inserting data of node at end of answer array and then reverse elements of our answer array.

Solve now