## DEV Community is a community of 699,738 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal TK
Sharing knowledge https://leandrotk.github.io
Originally published at leandrotk.github.io ・2 min read

This post is part of the Algorithms Problem Solving series.

## Problem description

This is the 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

``````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:

``````def bst_from_preorder(preorder):
root = TreeNode(preorder)

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