# 1008. Construct Binary Search Tree from Preorder Traversal
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
# Solution
Approach 1: recursive, upper and lower bounds.
Approach 2: recursive, binary search for boundaries.
Approach 3: iterative, using a stack.
# Code (Python)
Approach 1:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
# idea: give lower and upper bounds to subtrees, O(N)
return self._construct(preorder, -float('inf'), float('inf'))
def _construct(self, preorder, lower_bound, upper_bound):
if not preorder or preorder[0] >= upper_bound or preorder[0] <= lower_bound:
return None
root = TreeNode(preorder.pop(0))
root.left = self._construct(preorder, lower_bound, root.val)
root.right = self._construct(preorder, root.val, upper_bound)
return root
Approach 2:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
# idea: search for boundaries, O(NlogN)
return self._cons_bst(preorder, 0, len(preorder))
def _cons_bst(self, nums, start, end):
if start == end:
return None
root = TreeNode(nums[start])
index = bisect.bisect_left(nums, root.val, start + 1, end)
root.left = self._cons_bst(nums, start + 1, index)
root.right = self._cons_bst(nums, index, end)
return root
Approach 3:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
# idea: iterative. Use a stack to store nodes just like if we're doing trees to array.
if not preorder:
return None
root = TreeNode(preorder[0])
stack = [root]
for num in preorder[1:]:
if num < stack[-1].val:
stack[-1].left = TreeNode(num)
stack.append(stack[-1].left)
else:
while stack and stack[-1].val < num:
node = stack.pop()
node.right = TreeNode(num)
stack.append(node.right)
return root
# Code (C++)
Approach 1:
Approach 2: