Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal
Tags: algorithms, python, computerscience, interview
Published: 2020-06-17 11:36:05

---
title: Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal
published: true
description: Solving algorithms problems with TK
tags: algorithms, python, computerscience, interview
cover_image: https://raw.githubusercontent.com/leandrotk/tk/master/series/algorithms-problem-solving/assets/snow-tree.jpg
canonical_url: https://leandrotk.github.io/tk/series/algorithms-problem-solving/construct-binary-search-tree-from-preorder-traversal.html
series: Algorithms Problem Solving Series
---

This post is part of the [Algorithms Problem Solving](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html) series.

## Problem description

This is the [Construct Binary Search Tree from Preorder Traversal](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/) problem. The description looks like this:

Return the root node of a binary **search** tree that matches the given `preorder` traversal.

*(Recall that a binary search tree is a binary tree where for every node, any descendant of `node.left` has a value `<` `node.val`, and any descendant of `node.right` has a value `>` `node.val`. Also recall that a preorder traversal displays the value of the `node` first, then traverses `node.left`, then traverses `node.right`.)*

It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

## Examples

```python
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
```

## Solution

My idea was to build the root node with the first element of the list. Then iterate through the list from the index 1 to the last element of the list. For each item, I call helper to insert into the binary search tree.

The helper just follow the rules of insertion in a binary search tree:

- if value is smaller than the current node's value, go to the left
- if value is greater than the current node's value, go to the right
- Always look if the current node has a child. If it has, recursively call the helper passing the child.
- Otherwise, you can insert a new tree node with the new value

And the algorithm looks like this:

```python
def bst_from_preorder(preorder):
    root = TreeNode(preorder[0])

    for value in preorder[1:]:
        helper(root, value)

    return root

def helper(node, value):
    if value < node.val and node.left:
        helper(node.left, value)
    elif value < node.val:
        node.left = TreeNode(value)

    if value > node.val and node.right:
        helper(node.right, value)
    elif value > node.val:
        node.right = TreeNode(value)

    return node
```

## Resources

- [Learning Python: From Zero to Hero](https://leandrotk.github.io/tk/2017/09/learning-python-from-zero-to-hero/index.html)
- [Algorithms Problem Solving Series](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html)
- [Stack Data Structure](https://leandrotk.github.io/tk/2020/01/stack-data-structure/index.html)
- [Queue Data Structure](https://leandrotk.github.io/tk/2020/01/queue-data-structure/index.html)
- [Linked List](https://leandrotk.github.io/tk/2020/02/linked-list/index.html)
- [Tree Data Structure](https://leandrotk.github.io/tk/2020/02/tree-data-structure/index.html)