Simple Algorithm — Construct Binary Search Tree from Preorder Traversal

3 min readOct 14, 2020

Tree Traversal is one of the most popular topics that will be asked during FAANG interviews. This post will introduce one of the questions related to Binary Search Tree and Preorder Traversal.

When we are talking about Binary Search Tree (BST in short), the first thing we have learned is how to do the traversal on the tree to gather all node values we need for later processing.

There are three fundamental traversals that we use most often: Preorder, Inorder, and Postorder. This post may only focus on Preorder but you can see more about the other two in my other posts.

What is the Preorder traversal? We can start from the basic tree below.

We can see that the root has a value of 3 with 2 child nodes (2 and 5).

Since it is BST, the left child (if exists) always has a value smaller than its parent, on the other hand, the right child always has a value greater than its parent. When doing preorder traversal, we will first grab the root which is 3, then left child 2 and 5 on the right child at the end. The ‘pre’ means we access the parent first. And the order output after that would be

[ 3, 2, 5 ]

This post focuses on the questions when the list of node values is provided in specific sequences, then we need to construct the BST based on that.

Each node should have a similar data structure as below

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

For example, when the following preorder input is provided

int[] preorder = new int[] { 8, 5, 1, 7, 10, 12 };

We should be able to create a new tree with the following

One of the characteristics of Preorder Traversal is the first value in the list is always the root value and we can create the root node directly.

TreeNode root = new TreeNode(preorder[0]);

How do we process the array values after? Actually, we only need to understand 2 basic principles under BST as we mentioned before.

The left child always has a smaller value than the parent node
The right child always has a larger value than the parent node

Based on these 2 rules, we can go through the array and create the TreeNode necessary by comparing the node values.

for (int i = 1; i < preorder.length; i++) {
    buildTree(root, preorder[i]);
}
public void buildTree(TreeNode node, int value) {
    if (node == null) return;
    if (value < node.val) {
        if (node.left != null) {
            buildTree(node.left, value);
        } else {
            node.left = new TreeNode(value);
        }
    } else {
        if (node.right != null) {
            buildTree(node.right, value);
        } else {
            node.right = new TreeNode(value);
        }
    }
}

In this approach, it behaves similarly to the binary search when the result tree is in balance. It should cost O(log N) running time on each number and it beats 100% on Leetcode surprisingly.

Simple Algorithm — Construct Binary Search Tree from Preorder Traversal

Written by Daniel Tse