Constructing a binary tree from its preorder and inorder traversals involves rebuilding the tree using the order in which nodes are visited.
Preorder traversal visits the root node first, followed by the left and right subtrees, while inorder traversal visits the left subtree, root, and then the right subtree. By combining the two, we can uniquely reconstruct the binary tree. This is useful for problems where a tree’s structure needs to be determined from its traversal orders, such as restoring data or enabling traversal-based algorithms.
Understanding The Problem
You are provided with two integer arrays:
• preorder: The preorder traversal of a binary tree.
• inorder: The inorder traversal of the same binary tree.
Your goal is to reconstruct the binary tree from these traversal arrays and return the root node.
Before diving into the solution, let’s recall the traversal orders of a binary tree:
1. Preorder Traversal:
• The order is: Root → Left subtree → Right subtree.
• The first element of the preorder array is always the root of the tree.
2. Inorder Traversal:
• The order is: Left subtree → Root → Right subtree.
• In the inorder array, elements to the left of the root belong to the left subtree, and elements to the right belong to the right subtree.
Example
Let’s take an example to understand how the tree is constructed:
Input:
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
Output (Binary Tree):
3
/ \
9 20
/ \
15 7Key Insights to Solve the Problem
To reconstruct the binary tree, we need to leverage the following insights:
- Preorder Identifies the Root
In preorder traversal, the first element is always the root. During the reconstruction process:
• The first element of the preorder array is the root of the entire tree.
• For each recursive step, the next element of the preorder array is the root of the current subtree.
For example:
Preorder: [3, 9, 20, 15, 7]• Root of the tree: 3 (first element).
• Root of the left subtree: 9 (next in preorder after splitting).
• Root of the right subtree: 20.
2. Inorder Splits the Subtrees
In inorder traversal, the root splits the array into two parts:
• The elements to the left of the root in the inorder array form the left subtree.
• The elements to the right of the root form the right subtree.
Inorder: [9, 3, 15, 20, 7]If 3 is the root (from preorder):
• Left subtree: [9]
• Right subtree: [15, 20, 7]
This clear boundary allows us to recursively construct the left and right subtrees.
3. The Perfect Complement
• Preorder gives you the hierarchy of the tree (roots in sequence).
• Inorder provides the relationships and structure (left and right boundaries).
Together, they resolve the ambiguity of tree structure that would arise if we used just one traversal.
Why Do We Need the Inorder Traversal to Split the Tree?
If we only use preorder, we cannot determine:
1. Left and Right Subtree Sizes:
• Without knowing how many nodes belong to the left subtree, it’s impossible to decide where the right subtree starts in the preorder array.
2. Tree Structure:
• For example, a tree with identical preorder traversals can represent entirely different structures if we don’t have the inorder traversal.
Optimized Algorithm
We follow these steps:
1. Create a map of inorder values to their indices for fast lookups.
2. Start with the entire preorder and inorder arrays.
3. Recursively construct the tree:
• Pick the root from the preorder array.
• Find its position in the inorder array to determine the left and right subtrees.
• Recursively build the left and right subtrees.
4. Return the constructed tree.
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inorderMap = new HashMap<>();
// Build a map to store the index of each value in inorder traversal
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
// Start the recursive construction
return buildSubTree(preorder, inorderMap, 0, 0, inorder.length - 1);
}
private TreeNode buildSubTree(int[] preorder, Map<Integer, Integer> inorderMap, int preStart, int inStart, int inEnd) {
// Base case: if there are no elements to construct the tree
if (preStart >= preorder.length || inStart > inEnd) {
return null;
}
// Get the root value and create the root node
int rootValue = preorder[preStart];
TreeNode root = new TreeNode(rootValue);
// Find the root index in the inorder array
int inIndex = inorderMap.get(rootValue);
// Calculate the size of the left subtree
int leftTreeSize = inIndex - inStart;
// Recursively build the left and right subtrees
root.left = buildSubTree(preorder, inorderMap, preStart + 1, inStart, inIndex - 1);
root.right = buildSubTree(preorder, inorderMap, preStart + 1 + leftTreeSize, inIndex + 1, inEnd);
return root;
}
}
Step-by-Step Explanation
Step 1: Create an inorderMap
Map<Integer, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}• Without the hash map, finding the index of the root in the inorder array would require a linear scan, adding O(n) overhead for each recursive call.
• The hash map optimizes the process, reducing the overall time complexity of the solution to O(n).
2. Recursive Function buildSubTree
private TreeNode buildSubTree(int[] preorder, Map<Integer, Integer> inorderMap, int preStart, int inStart, int inEnd) {
if (preStart >= preorder.length || inStart > inEnd) {
return null;
}
}
• Binary trees are naturally recursive structures, making recursion a straightforward approach for traversal and construction.
3. Root Node Construction
int rootValue = preorder[preStart];
TreeNode root = new TreeNode(rootValue);• Retrieves the root value from the current position in the preorder array.
• Creates a new tree node with this value.
