Problem

Given a inorder and level order traversal, construct a binary tree from that.

Examples

Example 1:

1
2
3
4
5

            3
           / \
          9   20
             /  \
            15   7

1
2

Input: levelorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Similar Problems

Construct Binary Tree from Inorder and Preorder Traversal Construct Binary Tree from Inorder and Postorder Traversal

Solution

Method 1 - Recursion

Lets look at the binary tree:

1
2
3
4
5

         1
        / \
       2   3
      / \ / \
     4  5 6  7

The inorder and level-order traversal are:

1
2

inorder = [4, 2, 5, 1, 6, 3, 7]
levelOrder = [1, 2, 4, 5, 3, 6, 7]

How does levelOrder[] array helps? Elements in levelOrder[] give us levels to us, and we can start adding those elements in the tree.

How does inorder[] array helps? inorder[] helps determine the left and right subtrees of the root. Elements appearing before the root in inorder[] belong to the left subtree, while elements appearing after belong to the right subtree. In our case, it is [4, 2, 5] on left and [6, 3, 7] on right.

The algorithm starts by identifying the root (last element) from the level-order traversal. Then, it finds the inorder index i of the root element. Elements to the left (left subtree) and right (right subtree) of i in the inorder traversal are used to construct new arrays, newLeftLevel and newRightLevel, by extracting corresponding elements from the level-order traversal while maintaining their sequence. Finally, recursive calls are made to construct the left and right subtrees using these new arrays.

(See picture below).

Code

 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

class Solution {
    public TreeNode buildTree(int[] inorder, int[] levelOrder) {
        // Call the recursive function with full arrays and return the result
        return buildTree(inorder, levelOrder, 0, inorder.length - 1);
    }
	public TreeNode buildTree(int[] inorder, int[] levelOrder, int iStart, int iEnd) {
		if (iStart > iEnd) {
			return null;
		}

		int rootVal = levelOrder[0];
		TreeNode root = new Node(rootVal);

		if (iStart == iEnd) {
			return root;
		}

		int index = findIndex(inorder, rootVal, iStart, iEnd);

		int[] newleftLevel = newLevelOrder(inorder, levelOrder, iStart, index - 1);
		int[] newrighttLevel = newLevelOrder(inorder, levelOrder, index + 1, iEnd);

		root.left = buildTree(inorder, newleftLevel, iStart, index - 1);
		root.right = buildTree(inorder, newrighttLevel, index + 1, iEnd);

		return root;
	}

	public int[] newLevelOrder(int[] inorder, int[] levelOrder, int iStart, int iEnd) {
		int[] newlevel = new int[iEnd - iStart + 1];
		int x = 0;

		for (int i = 0; i < levelOrder.length; i++) {
			if (findIndex(inorder, levelOrder[i], iStart, iEnd) != -1) {
				newlevel[x] = levelOrder[i];
				x++;
			}
		}

		return newlevel;
	}

	public int findIndex(int[] inorder, int value, int iStart, int iEnd) {
		int x = -1;

		for (int i = iStart; i <= iEnd; i++) {
			if (value == inorder[i]) {
				x = i;
			}
		}

		return x;
	}
}