Last Updated: 22 Mar, 2021

Construct Binary Tree from Inorder and Postorder Traversal

Moderate

Asked in companies

Solve now

Problem statement

You are given arrays 'inOrder' and 'postOrder', which represent 'inorder' traversal and 'postorder' traversal of a 'Binary Tree' respectively.

Construct a 'Binary Tree' represented by the given arrays and return it's head.

Note:

Assume that the Binary Tree contains only unique elements.

Example:

Input: 'inOrder' = [9, 3, 15, 20, 7], 'postOrder' = [9, 15, 7, 20, 3]

Output:
We get the following binary tree from Inorder and Postorder traversal:

Input Format

The first line of each test case contains an integer 'n' which represents the number of nodes in the Binary Tree.

The next line of each test case contains 'n' single space-separated integers, representing the Postorder traversal of the Binary Tree.

The next line of each test case contains 'n' single space-separated integers, representing the Inorder traversal of the Binary Tree.

Output Format :

Return the head of the binary tree constructed.
The level order traversal of the Binary Tree is printed.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

To solve this problem, first, we take the last element in the ‘POST_ORDER’ array/list as the root because we know post-order traversal is like the first traverse of the left subtree nodes and then the right subtree node at the end traverse root. Hence the root is present as the last element of post-order traversal. Then we find the position of the root data in the ‘IN_ORDER’ array/list. Let’s assume at the ‘Kth’ index we find the root data in the ‘IN_ORDER’ array/list. Then we locate the range for the left subtree and right subtree and recursively call the function for finding the left subtree and the right subtree.

For example:

First, we select the last element of the ‘POST_ORDER’ array/list as a root. Then we find the 3 in the ‘IN_ORDER’ array/list. All the elements to the left of 3 in the ‘IN_ORDER’ array/list will be part of the left subtree and all the elements to the right of 3 in ‘IN_ORDER’ will be part of the right subtree as highlighted above.

The number of elements on the left side of the ‘IN_ORDER’ array/list is 1 in our example. So, 1 element in the ‘POST_ORDER’ array/list from starting will be part of the left subtree and the next elements less than the root index will be part of the right subtree.

Here is the algorithm:

We declare four variables ‘POST_START’, ‘POST_END’, ‘IN_START’, and ‘IN_END’ representing the starting and ending position of ‘POST_ORDER’ and ‘IN_ORDER’ respectively.
Base case: If ‘POST_START’ is greater than ‘POST_END’ or ‘IN_START’ is greater than ‘IN_END’:
- Return ‘NULL’.
We declare a variable ‘ROOT_VAL’ which is equal to ‘POST_ORDER[‘POST_END’]’.
We make a Binary Tree node using ‘ROOT_VAL’ as data of the node.
We declare a variable ‘ROOT_INDEX’ in which we store the index of root value that is present in the ‘IN_ORDER’ array/list.
We run a loop for ‘i’ = ‘IN_START’ to ‘IN_END’:
- If ‘ROOT_VAL’ is equal to ‘IN_ORDER[i]’:
  - ‘ROOT_INDEX’ is equal to ‘i’.
  - Break.
Now, the left subtree ‘IN_END’ is ‘ROOT_INDEX’ - 1 and ‘POST_END’ is ‘POST_START’ + ROOT_INDEX’ - 1 - ‘IN_START’.
The right subtree ‘IN_START’ is ‘ROOT_INDEX’ + 1 and ‘POST_START’ is ‘POST_START’ + ‘ROOT_INDEX’ - ‘IN_START’ and ‘POST_END’ is ‘POST_START’ - 1.
Now, we use recursion for finding the left subtree and the right subtree.
Finally, we return the ‘ROOT’ of the Binary Tree.

Solve now