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.
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.
classSolution {
privateint[] preorder;
privateint[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder ==null|| preorder.length== 0 || inorder.length== 0 || preLength != inLength) {
returnnull;
}
// We use indices to pass subarrays, which is more efficient than copying arrays on each call.this.preorder= preorder;
this.inorder= inorder;
int preLength = preorder.length;
int inLength = inorder.length;
return helper(preorder, inorder, 0, 0, inLength - 1);
}
private TreeNode helper(int preStart, int inStart, int inEnd) {
if (inStart > inEnd || preStart > preorder.length- 1) {
returnnull;
}
// Pick current node from Preorder traversal using preStart and increment preStart TreeNode root =new TreeNode(preorder[preStart]);
// If this node has no children then returnif (inStart == inEnd) {
return root;
}
// Else find the index of this node in Inorder traversalint inIndex = linearSearch(inorder, root.val, inStart, inEnd);
// Using index in Inorder traversal, construct left and right subtrees root.left= helper(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(preStart + inIndex - inStart + 1, inIndex + 1, inEnd);
return root;
}
staticintlinearSearch(int[] arr, int value, int start, int end) {
for (int i = start; i <= end; i++) {
if (arr[i]== value) {
return i;
}
}
return-1;
}
}
⏰ Time complexity: O(n^2) in the implementation shown above that uses linearSearch to locate the root in the inorder array. In the worst case (skewed trees), each recursive step performs an O(n) scan which leads to a quadratic total cost.
Optimized variant: O(n) if you precompute a hash map from value → inorder index before recursion; then each node is created and positioned in O(1) work.
🧺 Space complexity: O(n) total. The output tree stores n nodes; recursion stack uses O(h) auxiliary space where h is the tree height (worst-case O(n) for a skewed tree). The optimized variant additionally requires O(n) space for the index map.
Method 2 - Recursive Divide and Conquer with Inorder Index Mapping#
The naive approach has two main bottlenecks: the O(n) linear scan to find the root in the inorder array, and (in some implementations) the O(k) cost of slicing arrays at each step. We can eliminate both.
The problem states that all values are unique. This is the key that allows us to use a hash map to store the indices of the inorder elements, turning our O(n) search into an O(1) lookup.
To eliminate the slicing cost, we use indices to define the boundaries of our current subproblem for both arrays, ensuring we don’t create new arrays in memory.
classSolution {
privateint[] preorder;
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder= preorder;
this.inorderMap=new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
this.inorderMap.put(inorder[i], i);
}
return helper(0, 0, inorder.length- 1);
}
private TreeNode helper(int preStart, int inStart, int inEnd) {
// Base caseif (inStart > inEnd) {
returnnull;
}
// The root is the first element in the current preorder segmentint rootVal =this.preorder[preStart];
TreeNode root =new TreeNode(rootVal);
// Find root's index in O(1) using the mapint inIndex =this.inorderMap.get(rootVal);
// Calculate the size of the left subtreeint leftSubtreeSize = inIndex - inStart;
// Recursive calls are now identical in structure to the naive version root.left= helper(preStart + 1, inStart, inIndex - 1);
root.right= helper(preStart + 1 + leftSubtreeSize, inIndex + 1, inEnd);
return root;
}
}
classSolution:
defbuildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
self.preorder = preorder
self.inorder_map = {val: i for i, val in enumerate(inorder)}
return self.build_helper(0, 0, len(inorder) -1)
defbuild_helper(self, pre_start: int, in_start: int, in_end: int) -> Optional[TreeNode]:
# Base caseif in_start > in_end:
returnNone# The root is the first element in the current preorder segment root_val = self.preorder[pre_start]
root = TreeNode(root_val)
# Find root's index in O(1) using the map in_index = self.inorder_map[root_val]
# Calculate the size of the left subtree left_subtree_size = in_index - in_start
# Recursive calls are now identical in structure to the naive version root.left = self.build_helper(pre_start +1, in_start, in_index -1)
root.right = self.build_helper(pre_start +1+ left_subtree_size, in_index +1, in_end)
return root