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.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
Constraints:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder and inorder consist of unique values.inorder also appears in preorder.preorder is guaranteed to be the preorder traversal of the tree.inorder is guaranteed to be the inorder traversal of the tree.In #105 Construct Binary Tree from Preorder and Inorder Traversal, the key insight comes from understanding the properties of the two traversals. In preorder, the first element always represents the root of the current subtree. In inorder, elements to the left of the root belong to the left subtree, while elements to the right belong to the right subtree.
A common approach is to use recursion with divide and conquer. First, identify the root from the preorder array. Then locate that value in the inorder array to determine the boundaries of the left and right subtrees. To speed up lookups, store inorder indices in a hash map. Recursively construct the left and right subtrees using the corresponding ranges in the traversal arrays.
This strategy processes each node once, leading to efficient performance. With a hash map for quick index access, the algorithm runs in O(n) time with O(n) additional space for recursion and the lookup structure.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive Divide and Conquer with Hash Map | O(n) | O(n) |
| Recursive without Hash Map (linear search in inorder) | O(n^2) | O(n) |
take U forward
This approach uses recursion to build the tree. We know that the first element of the preorder traversal is the root of the tree. We find that element in the inorder traversal to determine the elements of the left and right subtrees. We then recursively build the left and right subtrees.
Steps:
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is processed once.
Space Complexity: O(n) for the recursion call stack and additional structures.
1import java.util.HashMap;
2import java.util.Map;
3
4public class Solution {
5 public static class TreeNode {
6 int val;
7 TreeNode left;
8 TreeNode right;
9 TreeNode(int x) { val = x; }
10 }
11
12 private Map<Integer, Integer> inorderIndexMap;
13 private int preorderIndex;
14
15 public TreeNode buildTree(int[] preorder, int[] inorder) {
16 inorderIndexMap = new HashMap<>();
17 for (int i = 0; i < inorder.length; i++) {
18 inorderIndexMap.put(inorder[i], i);
19 }
20 preorderIndex = 0;
21 return buildTree(preorder, 0, inorder.length - 1);
22 }
23
24 private TreeNode buildTree(int[] preorder, int inorderStart, int inorderEnd) {
25 if (inorderStart > inorderEnd) {
26 return null;
27 }
28
29 int rootVal = preorder[preorderIndex++];
30 TreeNode root = new TreeNode(rootVal);
31 int inorderRootIndex = inorderIndexMap.get(rootVal);
32
33 root.left = buildTree(preorder, inorderStart, inorderRootIndex - 1);
34 root.right = buildTree(preorder, inorderRootIndex + 1, inorderEnd);
35
36 return root;
37 }
38}In this Java implementation, a TreeNode class is defined. The buildTree method initializes the preorderIndex and the index map for inorder elements. The recursive helper method constructs the tree by selecting the current root from the preorder array and dividing the inorder array elements around it to build left and right subtrees.
This approach uses an iterative method to build the binary tree using stacks. By leveraging the properties of the preorder and inorder sequences, we can keep track of the tree nodes that are yet to be processed. We utilize a stack data structure to maintain the hierarchy of nodes as they are constructed.
Steps:
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the stack and additional data structures like the map for indices.
1function TreeNode(
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Preorder traversal always reveals the root of the current subtree first, while inorder traversal shows how nodes are split between the left and right subtrees. Combining these two pieces of information uniquely determines the structure of the binary tree. This property allows the original tree to be reconstructed.
Yes, this problem is a common medium-level tree question in technical interviews, including FAANG companies. It tests understanding of tree traversal properties, recursion, and divide-and-conquer strategies. Interviewers often expect candidates to optimize the solution using a hash map.
A hash map is commonly used to store the index of each element in the inorder traversal for fast lookups. This prevents repeated scanning of the inorder array and reduces the overall time complexity. Recursion is then used to build the binary tree structure.
The optimal approach uses recursion with a hash map to store the index of each value in the inorder traversal. The preorder array identifies the root of each subtree, while the inorder array determines left and right subtree boundaries. This allows the tree to be reconstructed efficiently in O(n) time.
This JavaScript solution provides an iterative mechanism for constructing the tree using a stack. It processes the preorder array and employs a map for inorder index positions to effectively manage node hierarchies without recursion.