Simple Algorithm - Construct Binary Search Tree from Preorder Traversal

Tree traversal is one of the classic interview topics, and binary search trees come up repeatedly. This walkthrough focuses on reconstructing a BST when the preorder traversal values are already provided.

Suppose each node looks like this:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

If the preorder input is:

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

Then the expected tree is:

The useful property of preorder traversal is that the first value is always the root:

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

From there, the problem reduces to repeated BST insertion:

• values smaller than the current node go left
• values larger than the current node go right

That leads to a simple recursive implementation:

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);
        }
    }
}

The approach is simple because it leans on the core BST invariant instead of over-optimizing too early. When the resulting tree stays balanced, the repeated insertion behavior resembles binary search and performs well enough for many interview-style inputs.