Construct Binary Tree from Preorder and Inorder Traversal
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.
Approach 1: DFS Recursive
class Solution {
int preorderIndex;
Map inorderIndexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
preorderIndex = 0;
// build a hashmap to store value -> its index relations
inorderIndexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderIndexMap.put(inorder[i], i);
}
return dfs(preorder, 0, preorder.length - 1);
}
private TreeNode dfs(int[] preorder, int left, int right) {
// if there are no elements to construct the tree
if (left > right)
return null;
// select the preorder_index element as the root and increment it
int rootValue = preorder[preorderIndex++];
TreeNode root = new TreeNode(rootValue);
// build left and right subtree
// excluding inorderIndexMap[rootValue] element because it's the root
root.left = dfs(preorder, left, inorderIndexMap.get(rootValue) - 1);
root.right = dfs(preorder, inorderIndexMap.get(rootValue) + 1, right);
return root;
}
}
Time Complexity: O(n) and Space Complexity: O(n)
Introduction
The problem "Construct Binary Tree from Preorder and Inorder Traversal" involves reconstructing a binary tree from its preorder and inorder traversals. Preorder traversal visits the nodes in the order: root, left subtree, right subtree. Inorder traversal visits nodes in the order: left subtree, root, right subtree.
Given these two traversals, we can uniquely reconstruct the binary tree. The key insight is that: - In preorder traversal, the first element is always the root. - In inorder traversal, the root divides the tree into left and right subtrees.
Problem Statement
Given two integer arrays `preorder` and `inorder` representing the preorder and inorder traversal of a binary tree, construct and return the binary tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
The tree node structure is given above. We need to reconstruct the binary tree from the provided traversals.
Approach
To solve this problem, we can use the following key observations:
- In preorder traversal, the first element is always the root of the tree or subtree.
- In inorder traversal, the root node divides the tree into left and right subtrees.
Based on these properties, the approach to reconstruct the tree can be described as follows:
- Start with the first element of the preorder array, which is the root of the tree.
- Locate the root element in the inorder array. All elements to the left of this root element in the inorder array represent the left subtree, and all elements to the right represent the right subtree.
- Recursively construct the left and right subtrees using the appropriate portions of the preorder and inorder arrays.
- Repeat this process until all nodes are placed in the correct position in the binary tree.
Algorithm
The algorithm for constructing the binary tree from preorder and inorder traversals can be described in the following steps:
- Start by taking the first element from the preorder array as the root.
- Find this root in the inorder array to split it into left and right subtrees.
- Recursively process the left and right subtrees by taking the corresponding elements from both the preorder and inorder arrays.
- Continue this process until the entire tree is constructed.
The recursive nature of this problem allows us to build the tree step by step, ensuring that each node is placed in the correct position according to the preorder and inorder sequences.
Example
Consider the following preorder and inorder traversals:
Preorder: [3, 9, 20, 15, 7]
Inorder: [9, 3, 15, 20, 7]
To construct the binary tree: - The first element of the preorder array is 3, which is the root. - In the inorder array, 3 is at index 1, meaning 9 is the left subtree and 15, 20, 7 form the right subtree. - Recursively construct the left subtree with preorder [9] and inorder [9]. - Recursively construct the right subtree with preorder [20, 15, 7] and inorder [15, 20, 7].
Tree:
3
/ \
9 20
/ \
15 7
In this example, the binary tree is successfully reconstructed, with 3 as the root, 9 as the left child, and 20 as the right child, which further branches into 15 and 7.
Code Implementation
Below is the Python implementation of the algorithm to construct the binary tree from preorder and inorder traversals:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
def helper(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
# Find the root in the inorder array to divide the tree
root_index_in_inorder = inorder.index(root_val)
# Recursively build the left and right subtrees
root.left = helper(preorder[1:1+root_index_in_inorder], inorder[:root_index_in_inorder])
root.right = helper(preorder[1+root_index_in_inorder:], inorder[root_index_in_inorder+1:])
return root
return helper(preorder, inorder)
In this code: - The function `buildTree` initializes the recursive process by calling the `helper` function. - The `helper` function processes the root node (first element of preorder), finds its position in the inorder array, and recursively constructs the left and right subtrees. - The recursive calls ensure that the correct portion of the preorder and inorder arrays is used to build the subtrees.
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. Each node is processed once, and the `inorder.index()` operation takes O(n) time. Thus, the overall time complexity is O(n^2).
The space complexity is O(n), where n is the number of nodes in the tree. This accounts for the space used by the recursion stack and the space required for storing the preorder and inorder arrays.
Conclusion
The "Construct Binary Tree from Preorder and Inorder Traversal" problem is a classic tree construction problem that tests your understanding of how different tree traversal methods work together. By leveraging the preorder and inorder sequences, we can recursively construct a binary tree with the correct structure. This problem is an excellent way to practice recursion and tree-building techniques.
