Construct BST from Preorder Traversal | LeetCode | Solution Explained
1008. Construct Binary Search Tree – BST from Preorder Traversal is a question which relies upon understanding the basics of binary search trees and traversals for trees. In this solution, I explain how we can think about this problem. Problem Link.
Basics: BSTs & Preorder Traversals
BST stands for Binary Search Tree. It has the structure
y < x < z that can be applied recursively.
Traversals are of three kind. They differ in how
x is accessed. Before, in-mid and after.
- Pre-order: x → y → z
- In-order: y → x → z
- Post-order: y → z → x
Let’s take a look at an example.
We can add the value
8 to the
10th node’s left, since
8 is smaller than
10. Similarly, we can keep on going for
Here’s when we have to be a bit more careful.
If we add the node
9 to the right child of parent
2, that looks like it would satisfy the property of BST. However,
9 can also be upgraded to the parent
5. Similarly to the parent
Each time, we are trying to assign a parent to the node
9. As in,
parent.right = child. However, we are also always trying to find a better parent – finally ending at the correct parent, which is the most upgraded one.
Isn’t this a bit complicated? How do we keep a track? We can use a stack.
As we go down the tree, we keep adding elements to the stack. At some point, when
parent.val < child.val, we start popping elements from the stack. In this way, we can keep going up the tree!
Let’s finally implement the solution for BST from preorder traversal.
Code for BST from Preorder 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 bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]: root = TreeNode(preorder) stack = [root] for val in preorder[1:]: parent, child = stack[-1], TreeNode(val) if parent.val > child.val: parent.left = child else: while stack and stack[-1].val < child.val: parent = stack.pop() parent.right = child stack.append(child) return root
June 13, 2022
January 24, 2022
January 20, 2022