Last Updated: 6 Dec, 2020
Construct Binary Tree From Inorder and Preorder Traversal
Easy
Asked in companies
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.
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 :
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.
Approaches
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:
- 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.
- Initially, set the value of “inStart” equal 0, “inEnd” equal to the size of the “inorder” sequence, and “pIndex” equal to 0.
- If “inStart” is greater than “inEnd” then return a NULL node because the subtree is empty.
- 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.
- If “inStart” and “inEnd” are equal, i.e., there is a single node in the given subtree. Therefore, return the root.
- Otherwise, find the index of “rootNode” in the inorder sequence and store it in a variable “inIndex”.
- Now, we can divide the inorder sequence of the given subtree into two parts i.e. [“inStart”, “inIndex” - 1] and [“inIndex” + 1, “inEnd”].
- 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”.
- 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”.
- Return the root node.
The basic idea of this approach is to use HashMap to store a key, value pair of <nodeValue, index> of the inorder sequence. Since we are searching the index of the root node in the inorder sequence in each recursive call, we can optimize it from O(N) to O(1) using HashMap.
Consider a recursive function “constructTree” which takes five arguments: “inStart”, “inEnd”, “pIndex”, “inorderIndex”, “preorder”. Here “inorderIndex” denotes HashMap to store a key, value pair of <nodeValue, index> , “preorder” denotes the preorder sequence of the binary tree respectively. 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.
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. The index of the root node can be found from “inorderIndex” and store in the variable “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:
- Consider a HashMap “inorderIndex” to store a key, value pair of <nodeValue, index> of the inorder sequence. Iterate over the inorder sequence and store the value of the inorder item as a key and index of that item as a value in the HashMap.
- Consider a recursive function “constructTree” which takes five arguments: “inStart”, “inEnd”, “pIndex”, “inorderIndex”, “preorder”. Here “inorderIndex” denotes HashMap to store a key, value pair of <nodeValue, index> , “preorder” denotes the preorder sequence of the binary tree respectively. 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.
- Initially, set the value of “inStart” equal 0, “inEnd” equal to the size of the “inorder” sequence, and “pIndex” equal to 0.
- If “inStart” is greater than “inEnd” then return a “NULL” node because the subtree is empty.
- 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.
- If “inStart” and “inEnd” are equal, i.e., there is a single node in the given subtree. Return the root.
- Otherwise, find the index of “rootNode” in the inorder sequence using “mp” and store it in a variable, i.e., “inIndex” = inorderIndex[rootNode]
- Now, we can divide the inorder sequence of given subtrees into two parts i.e. [“inStart”, “inIndex” - 1] and [“inIndex” + 1, “inEnd”].
- Recur for the left subtree by calling “constructTree” with arguments “inStart”, “inIndex” - 1, “pIndex”, “inorderIndex”, “preorder” and link the left child of the “rootNode” with the tree returned by the “constructTree”.
- Similarly, recur for the right subtree by calling “constructTree” with arguments “inIndex” + 1, “inEnd”, “pIndex”, “inorderIndex”, “preorder” and link the right child of the “rootNode” with the tree returned by the “constructTree”.
- Return the root node.