Leetcode 105: Construct Binary Tree from Preorder and Inorder Traversal
grid47 Exploring patterns and algorithms
Oct 27, 2024
6 min read
Solution to LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal Problem
Given two integer arrays, preorder and inorder, representing the preorder and inorder traversals of a binary tree, your task is to reconstruct and return the binary tree. The values in the arrays are unique, and the preorder traversal provides the sequence in which nodes are visited before their children, while the inorder traversal provides the order in which nodes are visited between their children.
Problem
Approach
Steps
Complexity
Input: The input consists of two arrays: `preorder` and `inorder`. `preorder` represents the preorder traversal of a binary tree, and `inorder` represents the inorder traversal of the same tree.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.
Output: You should return the root node of the binary tree constructed from the given preorder and inorder traversal arrays.
Example: Output: [4,2,6,1,3,5]
Constraints:
• The output should be the root node of the reconstructed binary tree.
Goal: The goal is to rebuild the binary tree by leveraging the properties of preorder and inorder traversals. In preorder, the first element is always the root, and the elements before it in inorder represent the left subtree, while the elements after it represent the right subtree.
Steps:
• First, create a mapping of each element's index in the inorder array.
• Then recursively pick elements from the preorder array to form the root, left, and right subtrees using the mapping from inorder.
Goal: You need to ensure the solution works efficiently for arrays with up to 3000 elements, given the constraints on the values of the elements.
Steps:
• The solution should handle up to 3000 nodes efficiently.
Assumptions:
• The input arrays represent valid preorder and inorder traversals of the same binary tree.
• Explanation: The binary tree can be reconstructed as follows: root is 3 (first in preorder), the left subtree is [9], and the right subtree is [20,15,7]. The resulting tree is:
3
/ \
9 20
/ \
15 7
This tree matches the given preorder and inorder traversals.
• Input: preorder = [1], inorder = [1]
• Explanation: The tree consists of a single node with value 1, forming a trivial tree where the preorder and inorder arrays both contain just the value [1].
• Explanation: The tree can be reconstructed by recognizing the root (10) from the preorder array, and the left and right subtrees by dividing the inorder array based on the root value.
Approach: To solve this problem, we use a recursive approach. By using the preorder array to determine the root nodes and the inorder array to determine the left and right subtrees, we can efficiently reconstruct the binary tree.
Observations:
• The first element of preorder is always the root, and inorder helps us identify the left and right subtrees.
• We can use a hashmap to quickly find the index of a node in the inorder array, allowing us to divide the array and construct the tree recursively.
Steps:
• Create a hashmap to store the index of each element in the inorder array.
• Use recursion to build the binary tree by picking the root from the preorder array and dividing the inorder array into left and right subtrees.
• Continue recursively for each subtree.
Empty Inputs:
• If either the preorder or inorder array is empty, return NULL as there is no tree to construct.
Large Inputs:
• Ensure the algorithm can handle arrays with up to 3000 elements efficiently.
Special Values:
• Handle trees where all nodes are either to the left or right (skewed trees).
Constraints:
• The arrays must contain unique values, ensuring no ambiguity when building the tree.
map<int, int> mp;
vector<int> preorder, inorder;
TreeNode*buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
this->inorder = inorder;
for(int i =0; i < inorder.size(); i++) mp[inorder[i]] = i;
return helper(0, 0, inorder.size() -1);
}
TreeNode*helper(int ps, int is, int ie) {
if(ps >= preorder.size() || is > ie) returnNULL;
TreeNode* root =new TreeNode(preorder[ps]);
root->left = helper(ps +1, is, mp[root->val] -1);
root->right = helper(ps + mp[root->val] - is +1, mp[root->val] +1, ie);
return root;
}
1 : Variable Declaration
map<int, int> mp;
Declare a map to store the index of each element from the inorder traversal for efficient look-up.
2 : Variable Declaration
vector<int> preorder, inorder;
Declare vectors to store the preorder and inorder traversal sequences of the tree.
