# 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.

We can add the value `8`

to the `10`

th 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

### 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