Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Examples

Example 1:

            3
           / \
          9   20
             /  \
            15   7

Input: preorder = [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 Postorder Traversal Construct Binary Tree from Inorder and Level Order Traversal

Solution

Method 1 - Recursion

Lets look at the binary tree:

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

The inorder and preorder traversal are:

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

How does preorder[] array helps? The first element in preorder[] acts as the root of the tree (in this case, 1).

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. (See picture below).

See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.

Code

Java
public TreeNode buildTree(int[] preorder, int[] inorder) {
	if (preorder == null || preorder.length == 0 || inorder.length == 0 || preLength != inLength) {
		return null;
	}

	int preLength = preorder.length;
	int inLength = inorder.length;
	return helper(preorder, inorder, 0, 0, inLength - 1);
}

	private static TreeNode helper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
	if (inStart > inEnd || preStart > preorder.length - 1) {
		return null;
	}

	// Pick current node from Preorder traversal using preStart and increment preStart
	TreeNode root = new TreeNode(preorder[preStart]);

	// If this node has no children then return
	if (inStart == inEnd) {
		return root;
	}

	// Else find the index of this node in Inorder traversal
	int inIndex = linearSearch(inorder, root.val, inStart, inEnd);

	// Using index in Inorder traversal, construct left and right subtrees
	root.left = helper(preorder, inorder, preStart + 1, inStart, inIndex - 1);
	// We are skipping the elements on the left of the current pre order node by adding inIndex - inStart + 1
	root.right = helper(preorder, inorder, preStart + inIndex - inStart + 1, inIndex + 1, inEnd);

	return root;
}


static int linearSearch(int[] arr, int value, int start, int end) {
	for (int i = start; i <= end; i++) {
		if (arr[i] == value) {
			return i;
		}
	}
	return -1;
}