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
BST property 
Preorder traversal
Observations
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 5 and 2.
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 8.
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[0])
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
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022
Furthest Building You Can Reach | LeetCode | Solution Explained
January 20, 2022