105. Construct Binary Tree from Preorder and Inorder Traversal Leetcode Solution
Construct Binary Tree from Preorder and Inorder Traversal Leetcode Problem :
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 :
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Construct Binary Tree from Preorder and Inorder Traversal Leetcode Solution :
Constraints :
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values.
- Each value of 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.
Example 1:
- Input: preorder = [-1], inorder = [-1]
- Output: [-1]
Intuition :
Inorder traversal is a special traversal that helps us to identify a node and its left and right subtree. Preorder traversal always gives us the root node as the first element. Using these properties we can construct the unique binary tree.
Approach :
- Create a map to store the inorder indexes.
- Call the function constructTree with all 7 parameters as shown above.
- In the recursive function, first check the base case, if (preStart,>preEnd || inStart> inEnd) then return NULL.
- Construct a node (say root) with the root value( first element of preorder).
- Find the index of the root, say elem from the hashmap.
- Find the number of elements ( say nElem) in the left subtree = elem – inStart
- Call recursively for the left subtree with correct values (shown in the above table) and store the answer received in root->left.
- Call recursively for the right subtree with correct values (shown in the above table) and store the answer received in root->right.
- Return root
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
TreeNode* buildTree(vector< int>& preorder, vector< int>& inorder) {
unordered_map< int, int> mp;
for (int i = 0; i < inorder.size(); i++) {
mp[inorder[i]] = i;
}
int n = preorder.size();
int m = inorder.size();
TreeNode* root = build(preorder, 0, n - 1, inorder, 0, m - 1, mp);
return root;
}
TreeNode* build(vector< int>& preorder, int preStart, int preEnd, vector< int>& inorder, int inStart, int inEnd, unordered_map< int, int>& mp) {
if (preStart > preEnd || inStart > inEnd)
return nullptr;
TreeNode* root = new TreeNode(preorder[preStart]);
int inRoot = mp[root->val];
int numLeft = inRoot - inStart;
root->left = build(preorder, preStart + 1, preStart + numLeft, inorder, inStart, inRoot - 1, mp);
root->right = build(preorder, preStart + numLeft + 1, preEnd, inorder, inRoot + 1, inEnd, mp);
return root;
}
};
Java
class Solution {
private int i = 0;
private int p = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, Integer.MIN_VALUE);
}
private TreeNode build(int[] preorder, int[] inorder, int stop) {
if (p >= preorder.length) {
return null;
}
if (inorder[i] == stop) {
++i;
return null;
}
TreeNode node = new TreeNode(preorder[p++]);
node.left = build(preorder, inorder, node.val);
node.right = build(preorder, inorder, stop);
return node;
}
}Python
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
VAL_TO_INORDER_IDX = {inorder[i]: i for i in range(len(inorder))}
def buildTreePartition(preorder, inorder_start, inorder_end):
if not preorder or inorder_start < 0 or inorder_end > len(inorder):
return None
root_val = preorder[0]
root_inorder_idx = VAL_TO_INORDER_IDX[root_val]
if root_inorder_idx > inorder_end or root_inorder_idx < inorder_start:
return None
root = TreeNode(preorder.pop(0))
root.left = buildTreePartition(preorder, inorder_start, root_inorder_idx - 1)
root.right = buildTreePartition(preorder, root_inorder_idx + 1, inorder_end)
return root
return buildTreePartition(preorder, 0, len(inorder) - 1)Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment