105. Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

Pattern: Related: 106. Construct Binary Tree from Inorder and Postorder Traversal

---

Solution

int[] preOrder;
int[] inOrder;
 
private TreeNode build(int pre, int inStart, int inEnd) {
	if (pre > preOrder.length - 1 || inStart > inEnd) return null;
 
	TreeNode root = new TreeNode(preOrder[pre]);
	int rootIn = inStart;
	while (inOrder[rootIn] != root.val) rootIn++;
	
	// preRight = pre + no. of els in preLeft
	int preLeft = pre + 1, preRight = pre + (rootIn - inStart + 1);
 
	root.left = build(preLeft, inStart, rootIn - 1);
	root.right = build(preRight, rootIn + 1, inEnd);
 
	return root;
}
 
public TreeNode buildTree(int[] preOrderArr, int[] inOrderArr) {
	preOrder = preOrderArr;
	inOrder = inOrderArr;
 
	return build(0, 0, inOrderArr.length - 1);
}

Notes

• preOrder gives you roots in sequence of preOrder traversal N L R
• so for each elment in preOrder → pre, all the elements before it in inOrder belong to its left subtree, and all the elements after it belong to its right subtree
• for each root = new TreeNode(preOrder[pre])
  • find rootIn (root index) in inOrder
  • calculate preLeft, and preRight (roots of the left and right subtree of root)
  • and inorder start and end inStart and inEnd
    • for left subtree : inStart -> rootIn-1 (current inorderStart to rootindex)
    • for right subtree : rootIn + 1 -> inEnd (rootIndex to current inorderEnd)
  • set the root.left and root.right to build() value of left and right ranges of inOrder and pre

Simplified Code

since build is traversing preorder, index for the preOrder array will increase desirably, eliminating the need for pre, preLeft, preRight

int[] preOrder;
int[] inOrder;
int index;
 
private TreeNode build(int inStart, int inEnd) {
	if (index > preOrder.length - 1 || inStart > inEnd) return null;
	
	TreeNode root = new TreeNode(preOrder[index++]);
	int pos = inStart;
	while (inOrder[pos] != root.val) pos++;
 
	root.left = build(inStart, pos - 1);
	root.right = build(pos + 1, inEnd);
 
	return root;
}
 
public TreeNode buildTree(int[] preOrderArr, int[] inOrderArr) {
	preOrder = preOrderArr;
	inOrder = inOrderArr;
	index = 0;
	return build(0, inOrderArr.length - 1);
}