# 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```
##### Tanishq Chaudhary

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.