Construct Binary Tree From Inorder and Preorder Traversal

Easy
0/40
Average time to solve is 10m
profile
Contributed by
72 upvotes
Asked in companies
AppleInfosysSwiggy

Problem statement

You have been given the preorder and inorder traversal of a binary tree. Your task is to construct a binary tree using the given inorder and preorder traversals.


Note: 
You may assume that duplicates do not exist in the given traversals.
For example : 
For the preorder sequence = [1, 2, 4, 7, 3] and the inorder sequence = [4, 2, 7, 1, 3], we get the following binary tree.

Example

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘N’ denoting the number of nodes in the binary tree.

The second line case contains ‘N’ integers denoting the preorder traversal of the binary tree.

The third line contains ‘N’ integers denoting the inorder traversal of the binary tree.
Output Format: 
Print the level order traversal of the constructed binary tree separated by a single-space.

For example, the output for the tree depicted in the below image would be :

Example

Level Order Traversal:   
1
2 3
4 5 6
7


Explanation :
Level 1 :
The root node of the tree is 1

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

Level 3 :
Left child of 2 = 4
Right child of 2 = null
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null
Right child of 4 = 7
Left child of 5 = null
Right child of 5 = null
Left child of 6 = null
Right child of 6 = null

Level 5 :
Left child of 7 = null
Right child of 7 = null
Note : 
Here, if the node is null, print nothing. The above format was just to provide clarity on how the output 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 output will be:

1 2 3 4 5 6 7
Note : 
You do not need to print anything; it has already been taken care of. You just need to return the root node of the constructed binary tree.
Sample Input 1:
5
1 2 4 7 3
4 2 7 1 3
Sample Output 1:
1 2 3 4 7

1 2 3
Explanation of Sample Input 1:
The tree after the construction is shown below.

Example

Sample Input 2:
2
1 2
2 1
Sample Output 2:
1 2
Constraints:
1 <= N <= 3000
1 <= data <= 10^4

Where ‘N’ is the total number of nodes in the binary tree, and “data” is the value of the binary tree node.


Time Limit: 1sec
Follow-up:
Can you solve this in O(N) time complexity?
Hint

Can you think of constructing the tree recursively?

Approaches (2)
Naive Approach

The basic idea of this approach is to build the tree recursively by utilizing the property of preorder and inorder traversal of a binary tree.

 

Consider a recursive function “constructTree” which takes five arguments: “inStart”, “inEnd”, “pIndex”, “inorder”, “preorder”. Here “inorder” and “preorder” as the inorder sequence and preorder sequence of the binary tree respectively. And, “inStart” and “inEnd” denote the starting and ending index of the inorder sequence of the given subtree and “pIndex” represents the index of the first element of the preorder sequence of the given subtree.

 

The node at index “pIndex” in the preorder traversal will be the root node of the binary tree. The idea here is to find the index of the root node in the inorder traversal because that index will divide the inorder traversal into two parts. For this, consider “inIndex” is equal to “inStart”. Then iterate over the inorder from “inStart” to “inEnd”. As we find the index of the root node in inorder, store it in “inIndex”. Now, the node from index “inStart” to “inIndex” - 1 are the inorder sequence of the left subtree of the root node and the node from index “inIndex” + 1 to “inEnd” are the inorder sequence of the right subtree.

 

Now, the problem is reduced to constructing the left and right subtree and then linking it to the root node. We can follow the same procedure and build the left and right subtree recursively.

 

Algorithm:

 

  1. Consider a recursive function “constructTree” which takes five arguments: “inStart”, “inEnd”, “pIndex”, “inorder”, “preorder”. Here “inorder” and “preorder” denote the inorder sequence and preorder sequence of the binary tree. And, “inStart” and “inEnd” represent the starting and ending index of the inorder sequence of the given subtree and “pIndex” denotes the index of the first element of the preorder sequence of the given subtree.
  2. Initially, set the value of “inStart” equal 0, “inEnd” equal to the size of the “inorder” sequence, and “pIndex” equal to 0.
  3. If “inStart” is greater than “inEnd” then return a NULL node because the subtree is empty.
  4. Assign the first element of the preorder sequence, denoted by “pIndex” in a variable, say “rootNode”. Make a new tree node with the “rootNode” value. And increment the “pIndex” by 1.
  5. If “inStart” and “inEnd” are equal, i.e., there is a single node in the given subtree. Therefore, return the root.
  6. Otherwise, find the index of “rootNode” in the inorder sequence and store it in a variable “inIndex”.
  7. Now, we can divide the inorder sequence of the given subtree into two parts i.e. [“inStart”, “inIndex” - 1] and [“inIndex” + 1, “inEnd”].
  8. Recur for the left subtree by calling “constructTree” with arguments “inStart”, “inIndex” - 1, “pIndex”, “inorder”, “preorder” and link the left child of the “rootNode” with the tree returned by the “constructTree”.
  9. Similarly, recur for the right subtree by calling “constructTree” with arguments “inIndex” + 1, “inEnd”, “pIndex”, “inorder”, “preorder” and link the right child of the “rootNode” with the tree returned by the “constructTree”.
  10. Return the root node.
Time Complexity

O(N ^ 2), Where ‘N’ is the number of nodes in the given binary tree.

 

Since we are constructing the tree recursively and each step we are iterating through the inorder sequence to find the index. There will be an ‘N’ recursive call, one for each node, and then a search in an inorder sequence of ‘N’ length. So, the overall time complexity will be O(N ^ 2).

Space Complexity

O(N), Where ‘N’ is the number of nodes in the given binary tree.

 

Since we are doing a recursive tree traversal and in the worst case (Skewed Trees), all nodes of the given tree can be stored in the call stack. So the overall space complexity will be O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Construct Binary Tree From Inorder and Preorder Traversal
Full screen
Console