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

Observations

Let’s take a look at an example.

Example for the question BST from Preorder traversal

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

    Leave a Reply

    Your email address will not be published. Required fields are marked *