Construct Binary Search Tree from Preorder Traversal

Photo by Esther Wilhelmsson

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[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
• Algorithms Problem Solving Series
• Stack Data Structure
• Queue Data Structure
• Linked List
• Tree Data Structure

Have fun, keep learning, and always keep coding!

My Twitter and Github