Construct Binary Search Tree from Preorder Traversal

Construct Binary Search Tree from Preorder Traversal - Problem

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Input & Output

Example 1 — Basic BST

$ Input: preorder = [8,5,1,7,10,12]

› Output: [8,5,10,1,7,null,12]

💡 Note: Preorder traversal visits root first (8), then left subtree (5,1,7), then right subtree (10,12). Reconstructed tree maintains BST property.

Example 2 — Single Node

$ Input: preorder = [1]

› Output: [1]

💡 Note: Single node forms a tree with just the root.

Example 3 — Right Skewed Tree

$ Input: preorder = [1,3,5,7]

› Output: [1,null,3,null,5,null,7]

💡 Note: Each node only has a right child, forming a right-skewed tree.

Constraints

1 ≤ preorder.length ≤ 100
1 ≤ preorder[i] ≤ 10⁸
The values of preorder are unique

Visualization

Tap to expand

Understanding the Visualization

Input Array

Preorder traversal: [8,5,1,7,10,12]

BST Construction

Build tree following BST properties

Level-order Output

Return array representation: [8,5,10,1,7,null,12]

Key Takeaway

🎯 Key Insight: Use BST property constraints or monotonic stack to efficiently place each node in correct position

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to use the BST property to determine node placement. The stack approach is optimal - maintain a monotonic decreasing stack of potential parents and attach each new node appropriately. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack Approach	O(n)	O(n)	Use a monotonic decreasing stack to track ancestors and build tree efficiently
Recursive with Bounds	O(n²)	O(n)	Use recursion with min/max bounds to place each node correctly

Monotonic Stack Approach — Algorithm Steps

Initialize empty stack
For each value in preorder, create new node
Pop stack elements smaller than current value
Attach node as right child of last popped or left child of stack top

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Stack

Start with root node in stack

Process Each Node

Pop smaller ancestors, attach to last popped or stack top

Maintain Invariant

Stack contains decreasing sequence of potential parents

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void printArray(struct TreeNode* root) {
    if (!root) {
        printf("[]");
        return;
    }
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    int result[1000];
    int resultSize = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (node) {
            result[resultSize++] = node->val;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        }
    }
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("%d", result[i]);
        if (i < resultSize - 1) printf(",");
    }
    printf("]");
}

struct TreeNode* solution(int* preorder, int size) {
    if (size == 0) return NULL;
    
    struct TreeNode* root = createNode(preorder[0]);
    struct TreeNode* stack[1000];
    int stackSize = 1;
    stack[0] = root;
    
    for (int i = 1; i < size; i++) {
        struct TreeNode* node = createNode(preorder[i]);
        struct TreeNode* parent = NULL;
        
        while (stackSize > 0 && stack[stackSize-1]->val < node->val) {
            parent = stack[stackSize-1];
            stackSize--;
        }
        
        if (parent) {
            parent->right = node;
        } else {
            stack[stackSize-1]->left = node;
        }
        
        stack[stackSize++] = node;
    }
    
    return root;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int preorder[100];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        preorder[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    struct TreeNode* root = solution(preorder, size);
    printArray(root);
    printf("\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through preorder array, each element pushed and popped at most once

✓ Linear Growth

Space Complexity

O(n)

Stack stores at most n nodes in worst case

⚡ Linearithmic Space

187.0K Views

Medium Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler