Techie Delight
Coding made easy
Write an efficient algorithm to construct a binary tree from given inorder and level-order sequence.
For example,
Input:
Inorder Traversal : { 4, 2, 5, 1, 6, 3, 7 }
Level-order Traversal : { 1, 2, 3, 4, 5, 6, 7 }
Output: Below binary tree
The idea is to start with the root node which would be the node with minimum index in level-order sequence and partition the inorder sequence for left and right subtree. To find the boundary of left and right subtree, search for index of the root node in inorder sequence. Then all keys before the root node in inorder sequence becomes part of the left subtree and all keys after the root node becomes part of the right subtree. We repeat this recursively for all nodes in the tree, and construct the tree in the process.
To illustrate, consider below inorder and level-order sequence –
Inorder : { 4, 2, 5, 1, 6, 3, 7 }
Level-order : { 1, 2, 3, 4, 5, 6, 7 }
Root node is present at first index in the level-order sequence i.e. node 1 is the root node. Now since node 1 is the root, all nodes before node 1 i.e. {4, 2, 5} in the inorder sequence must be included in the left subtree of the root node and all the nodes after node 1 i.e. {6, 3, 7} must be included in the right subtree. This reduces the problem into building the left and right subtrees and linking them to the root node.
Left subtree:
Inorder : { 4, 2, 5 }
Level-order : { 1, 2, 3, 4, 5, 6, 7 }
Right subtree:
Inorder : { 6, 3, 7 }
Level-order : { 1, 2, 3, 4, 5, 6, 7 }
In the respective inorder sequence, the key which appears first in the level-order traversal becomes the root node for the corresponding left or right subtree. This is demonstrated below in C++, Java and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;
// Data structure to store a Binary Tree node
struct Node {
int data;
Node* left, *right;
};
// Function to create a new binary tree node having given key
Node* newNode(int key)
{
Node* node = new Node;
node->data = key;
node->left = node->right = nullptr;
return node;
}
// Recursive function to perform inorder traversal of a binary tree
void inorderTraversal(Node* root)
{
if (root == nullptr)
return;
inorderTraversal(root->left);
cout << root->data << ” “;
inorderTraversal(root->right);
}
// Recursive function to construct a binary tree from in-order and
// level-order traversals
Node* buildTree(int inorder[], int start, int end,
unordered_map<int, int> map)
{
// base case
if (start > end)
return nullptr;
// find the index of root node in inorder[] to determine the
// boundary of left and right subtree
int index = start;
for (int j = start + 1; j <= end; j++)
{
// find node with minimum index in level-order traversal
// That would be the root node of inorder[start, end]
if (map[inorder[j]] < map[inorder[index]])
index = j;
}
// construct the root node
Node* root = newNode(inorder[index]);
// recursively construct the left subtree
root->left = buildTree(inorder, start, index – 1, map);
// recursively construct the right subtree
root->right = buildTree(inorder, index + 1, end, map);
// return root node
return root;
}
// Construct a binary tree from in-order and level-order traversals
Node* buildTree(int in[], int level[], int n)
{
// create a map to efficiently find index of an element in
// level-order sequence
unordered_map<int, int> map;
for (int i = 0; i < n; i++)
map[level[i]] = i;
// Construct the tree and return it
return buildTree(in, 0, n – 1, map);
}
int main()
{
int inorder[] = { 4, 2, 5, 1, 6, 3, 7 };
int level[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(inorder)/sizeof(inorder[0]);
Node* root = buildTree(inorder, level, n);
cout << “Inorder traversal of the constructed tree: “;
inorderTraversal(root);
return 0;
}
|
Output:
Inorder traversal of the constructed tree: 4 2 5 1 6 3 7
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
import java.util.HashMap;
import java.util.Map;
// Data structure to store a Binary Tree node
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
}
}
class Main
{
// Recursive function to perform inorder traversal of a binary tree
public static void inorderTraversal(Node root)
{
if (root == null) {
return;
}
inorderTraversal(root.left);
System.out.print(root.data + ” “);
inorderTraversal(root.right);
}
// Recursive function to construct a binary tree from in-order and
// level-order traversals
public static Node buildTree(int[] inorder, int start, int end,
Map<Integer, Integer> map)
{
// base case
if (start > end) {
return null;
}
// find the index of root node in inorder[] to determine the
// boundary of left and right subtree
int index = start;
for (int j = start + 1; j <= end; j++)
{
// find node with minimum index in level order traversal
// That would be the root node of inorder[start, end]
if (map.get(inorder[j]) < map.get(inorder[index])) {
index = j;
}
}
// construct the root node
Node root = new Node(inorder[index]);
// recursively construct the left subtree
root.left = buildTree(inorder, start, index – 1, map);
// recursively construct the right subtree
root.right = buildTree(inorder, index + 1, end, map);
// return root node
return root;
}
// Construct a binary tree from in-order and level-order traversals
public static Node buildTree(int[] in, int[] level)
{
// create a map to efficiently find index of an element in
// level-order sequence
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
map.put(level[i], i);
}
// Construct the tree and return it
return buildTree(in, 0, in.length – 1, map);
}
public static void main(String[] args)
{
int[] inorder = { 4, 2, 5, 1, 6, 3, 7 };
int[] level = { 1, 2, 3, 4, 5, 6, 7 };
Node root = buildTree(inorder, level);
System.out.print(“Inorder traversal of the constructed tree: “);
inorderTraversal(root);
}
}
|
Output:
Inorder traversal of the constructed tree: 4 2 5 1 6 3 7
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
# Data structure to store a Binary Tree node
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
# Recursive function to perform inorder traversal of a binary tree
def inorderTraversal(root):
if root is None:
return
inorderTraversal(root.left)
print(root.data, end=‘ ‘)
inorderTraversal(root.right)
# Recursive function to construct a binary tree from in-order and
# level-order traversals
def buildTree(inorder, start, end, dict):
# base case
if start > end:
return None
# find the index of root node in inorder to determine the
# boundary of left and right subtree
index = start
for j in range(start + 1, end + 1):
# find node with minimum index in level order traversal
# That would be the root node of inorder[start, end]
if dict.get(inorder[j]) < dict.get(inorder[index]):
index = j
# construct the root node
root = Node(inorder[index])
# recursively construct the left subtree
root.left = buildTree(inorder, start, index – 1, dict)
# recursively construct the right subtree
root.right = buildTree(inorder, index + 1, end, dict)
# return root node
return root
# Construct a binary tree from in-order and level-order traversals
def buildBT(inorder, level):
# create a dictionary to efficiently find index of an element in
# level-order sequence
dict = {}
for i, e in enumerate(level):
dict[e] = i
# Construct the tree and return it
return buildTree(inorder, 0, len(inorder) – 1, dict)
if __name__ == ‘__main__’:
inorder = [4, 2, 5, 1, 6, 3, 7]
level = [1, 2, 3, 4, 5, 6, 7]
root = buildBT(inorder, level)
print(“Inorder traversal of the constructed tree: “, end=”)
inorderTraversal(root)
|
Output:
Inorder traversal of the constructed tree: 4 2 5 1 6 3 7
Download Run Code
Output:
Inorder traversal of the constructed tree: 4 2 5 1 6 3 7
Download Run Code
Output:
Inorder traversal of the constructed tree: 4 2 5 1 6 3 7
Download Run Code
Output:
Inorder traversal of the constructed tree: 4 2 5 1 6 3 7
The time complexity of above solution is O(n2) and requires O(n) extra space for map and recursive call stack.