Home

Construct Binary Search Tree from Preorder Traversal


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:

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

Have fun, keep learning, and always keep coding!

My Twitter and Github

Patreon Become a Patron Coffee icon Buy me a coffee