Construct Binary Tree From Preorder And Inorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
You are given two integer arrays, preorder and inorder:
- preorder represents the preorder traversal of a binary tree.
- inorder represents the inorder traversal of the same tree.
- Both arrays have the same length and contain unique values.
Your task is to reconstruct the binary tree using these traversals and return its root.
Example 1:
Illustration :
Input: preorder = [1,2,3,4], inorder = [2,1,3,4]
Output: [1,2,3,null,null,null,4]
Output: [1,2,3,null,null,null,4]
Example 2:
- Input: preorder = [1], inorder = [1]
- Output: [1]
Constraints:
- 1 <= inorder.length <= 1000.
- inorder.length == preorder.length
- -1000 <= preorder[i], inorder[i] <= 1000
Hints to Solve Construct Binary Tree From Preorder And Inorder Traversal
Recommendation for Time and Space Complexity:
Aim for a solution with O(n) time and O(n) space, where n is the total number of nodes in the tree.
Hint 1 :
The inorder traversal splits the tree into two parts: the left and right subtrees based on the root node. Can you determine the root’s position in the inorder array using the preorder array?
Hint 2 :
In preorder traversal, the first node is always the root. Use this property to start reconstructing the binary tree.
Hint 3 :
Once you identify the root node from the preorder array, find its position in the inorder array. While a linear search works, it results in O(n^2) complexity. Is there a faster way to do this?
Hint 4 :
Using a hash map allows you to find the index of any node in the inorder array in O(1) time. Think about how you can build and use this efficiently.
Hint 5:
Use Depth First Search (DFS) for tree construction. Track the current index in the preorder array globally and use two pointers (l and r) to define the inorder segment for the current subtree.
For each node, create it, find its position using the hash map, and recursively build the left and right subtrees.
There are mainly 3 approach to solve this problem:
- Depth First Search Method (DFS)
- Hash Map Method
- Depth First Search (Optimal)
1. Depth First Search Method
Use the preorder array to identify the root node and divide the inorder array into left and right subtrees. Recursively repeat this process to construct the entire binary tree.
- Time complexity: O(n^2)
- Space complexity: O(n^2)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
if (preorder.empty() || inorder.empty()) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[0]);
auto mid = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();
vector leftPre(preorder.begin() + 1, preorder.begin() + mid + 1);
vector rightPre(preorder.begin() + mid + 1, preorder.end());
vector leftIn(inorder.begin(), inorder.begin() + mid);
vector rightIn(inorder.begin() + mid + 1, inorder.end());
root->left = buildTree(leftPre, leftIn);
root->right = buildTree(rightPre, rightIn);
return root;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
int mid = -1;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == preorder[0]) {
mid = i;
break;
}
}
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, mid + 1);
int[] leftInorder = Arrays.copyOfRange(inorder, 0, mid);
root.left = buildTree(leftPreorder, leftInorder);
int[] rightPreorder = Arrays.copyOfRange(preorder, mid + 1, preorder.length);
int[] rightInorder = Arrays.copyOfRange(inorder, mid + 1, inorder.length);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
}
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])
return root
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
buildTree(preorder, inorder) {
if (!preorder.length || !inorder.length) {
return null;
}
let root = new TreeNode(preorder[0]);
let mid = inorder.indexOf(preorder[0]);
root.left = this.buildTree(
preorder.slice(1, mid + 1),
inorder.slice(0, mid),
);
root.right = this.buildTree(
preorder.slice(mid + 1),
inorder.slice(mid + 1),
);
return root;
}
}
2. Hash Map Method
Build a hash map to store the index of each value in the inorder array for quick lookup. This avoids linear searches, improving efficiency while constructing the tree.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int pre_idx = 0;
unordered_map indices;
TreeNode* dfs(vector& preorder, int l, int r) {
if (l > r) return nullptr;
int root_val = preorder[pre_idx++];
TreeNode* root = new TreeNode(root_val);
int mid = indices[root_val];
root->left = dfs(preorder, l, mid - 1);
root->right = dfs(preorder, mid + 1, r);
return root;
}
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
for (int i = 0; i < inorder.size(); ++i) {
indices[inorder[i]] = i;
}
return dfs(preorder, 0, inorder.size() - 1);
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
int pre_idx = 0;
HashMap indices = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
indices.put(inorder[i], i);
}
return dfs(preorder, 0, inorder.length - 1);
}
private TreeNode dfs(int[] preorder, int l, int r) {
if (l > r) return null;
int root_val = preorder[pre_idx++];
TreeNode root = new TreeNode(root_val);
int mid = indices.get(root_val);
root.left = dfs(preorder, l, mid - 1);
root.right = dfs(preorder, mid + 1, r);
return root;
}
}
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
indices = {val: idx for idx, val in enumerate(inorder)}
self.pre_idx = 0
def dfs(l, r):
if l > r:
return None
root_val = preorder[self.pre_idx]
self.pre_idx += 1
root = TreeNode(root_val)
mid = indices[root_val]
root.left = dfs(l, mid - 1)
root.right = dfs(mid + 1, r)
return root
return dfs(0, len(inorder) - 1)
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
buildTree(preorder, inorder) {
let pre_idx = 0;
let indices = new Map();
inorder.forEach((val, i) => indices.set(val, i));
function dfs(l, r) {
if (l > r) return null;
let root_val = preorder[pre_idx++];
let root = new TreeNode(root_val);
let mid = indices.get(root_val);
root.left = dfs(l, mid - 1);
root.right = dfs(mid + 1, r);
return root;
}
return dfs(0, inorder.length - 1);
}
}
3. Depth First Search (Optimal) Method
Combine DFS with a hash map for faster root lookups. Use a global pointer to track the current root index in the preorder array and efficiently split the inorder array into left and right subtrees.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int preIdx = 0;
int inIdx = 0;
TreeNode* dfs(vector& preorder, vector& inorder, int limit) {
if (preIdx >= preorder.size()) return nullptr;
if (inorder[inIdx] == limit) {
inIdx++;
return nullptr;
}
TreeNode* root = new TreeNode(preorder[preIdx++]);
root->left = dfs(preorder, inorder, root->val);
root->right = dfs(preorder, inorder, limit);
return root;
}
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
return dfs(preorder, inorder, INT_MAX);
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
int preIdx = 0;
int inIdx = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return dfs(preorder, inorder, Integer.MAX_VALUE);
}
private TreeNode dfs(int[] preorder, int[] inorder, int limit) {
if (preIdx >= preorder.length) return null;
if (inorder[inIdx] == limit) {
inIdx++;
return null;
}
TreeNode root = new TreeNode(preorder[preIdx++]);
root.left = dfs(preorder, inorder, root.val);
root.right = dfs(preorder, inorder, limit);
return root;
}
}
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
preIdx = inIdx = 0
def dfs(limit):
nonlocal preIdx, inIdx
if preIdx >= len(preorder):
return None
if inorder[inIdx] == limit:
inIdx += 1
return None
root = TreeNode(preorder[preIdx])
preIdx += 1
root.left = dfs(root.val)
root.right = dfs(limit)
return root
return dfs(float('inf'))
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
buildTree(preorder, inorder) {
let preIdx = 0, inIdx = 0;
function dfs(limit) {
if (preIdx >= preorder.length) return null;
if (inorder[inIdx] === limit) {
inIdx++;
return null;
}
let root = new TreeNode(preorder[preIdx++]);
root.left = dfs(root.val);
root.right = dfs(limit);
return root;
}
return dfs(Infinity);
}
}
