Solution 1Index Map
- TimeO(n^2)
- SpaceO(n^2). where, n is number of nodes
This is a sub par solution, but is easy to think of and implement. Better solution has a time complexity of O(n).
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]:
'''
Time Complexity: O(n^2)
Space Complexity: O(n^2). where, n is number of nodes
This is a sub par solution, but is easy to think of and implement. Better solution has a time complexity of O(n).
'''
n = len(preorder)
index = {num: i for i, num in enumerate(inorder)}
def subTree(preStart: int, preEnd: int, inStart: int, inEnd: int) -> Optional[TreeNode]:
if preStart == preEnd:
return None
root = TreeNode(preorder[preStart])
treeLen = index[root.val] + 1 - inStart
root.left = subTree(preStart + 1, preStart + treeLen, inStart, inStart + treeLen - 1)
root.right = subTree(preStart + treeLen, preEnd, inStart + treeLen, inEnd)
return root
return subTree(0, n, 0, n)Solution 2List Slicing
- TimeO(n^2)
- SpaceO(n^2). where, n is number of nodes, stack trace and list slicing are causes
This is a sub par solution, but is easy to think of and implement. Better solution has a time and space complexities of O(n).
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]:
'''
Time Complexity: O(n^2)
Space Complexity: O(n^2). where, n is number of nodes, stack trace and list slicing are causes.
This is a sub par solution, but is easy to think of and implement. Better solution has a time and space complexities of O(n).
'''
if not preorder:
return None
root = TreeNode(preorder[0])
leftLimit = inorder.index(root.val)+1
root.left = self.buildTree(preorder[1:leftLimit], inorder[:leftLimit-1])
root.right = self.buildTree(preorder[leftLimit:], inorder[leftLimit:])
return rootSolution 3Index Scan
- TimeO(n^2)
- SpaceO(n). where, n is number of nodes, this is because of stacktrace, we eliminated list slicing in this approach
This is a sub par solution, better than slicing lists though. Better solution has a time and space complexities of O(n).
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]:
'''
Time Complexity: O(n^2)
Space Complexity: O(n). where, n is number of nodes, this is because of stacktrace, we eliminated list slicing in this approach.
This is a sub par solution, better than slicing lists though. Better solution has a time and space complexities of O(n).
'''
n = len(preorder)
def subTree(preStart: int, preEnd: int, inStart: int, inEnd: int) -> Optional[TreeNode]:
if preStart == preEnd:
return None
root = TreeNode(preorder[preStart])
treeLen = inorder.index(root.val, inStart, inEnd) + 1 - inStart
root.left = subTree(preStart + 1, preStart + treeLen, inStart, inStart + treeLen - 1)
root.right = subTree(preStart + treeLen, preEnd, inStart + treeLen, inEnd)
return root
return subTree(0, n, 0, n)Solution 4Optimal Index Map
- TimeO(n)
- SpaceO(n). where, n is number of nodes, because of stacktrace
This is an optimal solution, but there is even better optimized solution with same time and space complexities.
This is good for interview purposes. Refer https://neetcode.io/solutions/construct-binary-tree-from-preorder-and-inorder-traversal
# 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]:
'''
Time Complexity: O(n)
Space Complexity: O(n). where, n is number of nodes, because of stacktrace.
This is an optimal solution, but there is even better optimized solution with same time and space complexities.
This is good for interview purposes. Refer https://neetcode.io/solutions/construct-binary-tree-from-preorder-and-inorder-traversal
'''
n = len(preorder)
index = {num: i for i, num in enumerate(inorder)}
def subTree(preStart: int, preEnd: int, inStart: int, inEnd: int) -> Optional[TreeNode]:
if preStart == preEnd:
return None
root = TreeNode(preorder[preStart])
treeLen = index[root.val] + 1 - inStart
root.left = subTree(preStart + 1, preStart + treeLen, inStart, inStart + treeLen - 1)
root.right = subTree(preStart + treeLen, preEnd, inStart + treeLen, inEnd)
return root
return subTree(0, n, 0, n)/**
* 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;
* }
* }
*/
private int[] preorder;
private int[] inorder;
private HashMap<Integer, Integer> index;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
this.index = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
this.index.put(inorder[i], i);
}
return tree(0, preorder.length, 0, inorder.length);
}
public TreeNode tree(int p1, int p2, int i1, int i2) {
if ( p1 == p2 ) {
return null;
}
TreeNode root = new TreeNode(preorder[p1]);
int len = index.get(root.val) - i1 + 1;
root.left = tree(p1 + 1, p1 + len, i1, i1 + len);
root.right = tree(p1 + len, p2, i1 + len, i2);
return root;
}