Depth of BST Given Insertion Order - Practice Coding Problems

Depth of BST Given Insertion Order - Problem

You are given a 0-indexed integer array order of length n, a permutation of integers from 1 to n representing the order of insertion into a binary search tree.

A binary search tree is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

The binary search tree is constructed as follows:

order[0] will be the root of the binary search tree.
All subsequent elements are inserted as the child of any existing node such that the binary search tree properties hold.

Return the depth of the binary search tree. A binary tree's depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Input & Output

Example 1 — Balanced Tree

$ Input: order = [2,1,4,3]

› Output: 3

💡 Note: Insert 2 (root), 1 (left of 2), 4 (right of 2), 3 (left of 4). Longest path: 2→4→3 with depth 3.

Example 2 — Right Skewed Tree

$ Input: order = [1,2,3,4,5]

› Output: 5

💡 Note: Each element goes to the right, creating a linear tree: 1→2→3→4→5 with depth 5.

Example 3 — Single Node

$ Input: order = [1]

› Output: 1

💡 Note: Only one node, so the depth is 1.

Constraints

1 ≤ order.length ≤ 1000
1 ≤ order[i] ≤ order.length
All integers in order are unique.

Visualization

Tap to expand

Understanding the Visualization

Input

Array representing insertion order: [2,1,4,3]

Build BST

Insert elements following BST properties

Calculate Depth

Find longest path from root to leaf

Key Takeaway

🎯 Key Insight: BST depth is determined by the insertion sequence - different orders create different tree shapes

Asked in

a Amazon 45 G Google 35 M Microsoft 30 f Facebook 25

The key insight is that BST depth depends on insertion order - some sequences create balanced trees while others create skewed ones. The optimal approach uses recursive depth calculation without building actual tree nodes. Time: O(n²), Space: O(n) for recursion stack.

Common Approaches

Approach	Time	Space	Notes
✓ Build Tree and Measure Depth	O(n²)	O(n)	Construct the entire BST then calculate its maximum depth
Recursive Depth Calculation	O(n²)	O(n)	Calculate depth without building actual tree nodes using recursion

Build Tree and Measure Depth — Algorithm Steps

Create TreeNode class structure
Insert each element following BST properties
Perform DFS to calculate maximum depth

Visualization

Tap to expand

Step-by-Step Walkthrough

Insert Elements

Build BST by inserting elements in given order

Tree Structure

Visualize the resulting binary search tree

Calculate Depth

Find longest path from root to leaf

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 insertNode(struct TreeNode* root, int val) {
    if (val < root->val) {
        if (root->left == NULL) {
            root->left = createNode(val);
        } else {
            insertNode(root->left, val);
        }
    } else {
        if (root->right == NULL) {
            root->right = createNode(val);
        } else {
            insertNode(root->right, val);
        }
    }
}

int calculateDepth(struct TreeNode* root) {
    if (root == NULL) return 0;
    int left = calculateDepth(root->left);
    int right = calculateDepth(root->right);
    return 1 + (left > right ? left : right);
}

int solution(int* order, int size) {
    if (size == 0) return 0;
    
    struct TreeNode* root = createNode(order[0]);
    for (int i = 1; i < size; i++) {
        insertNode(root, order[i]);
    }
    
    return calculateDepth(root);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int order[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            order[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(order, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case (sorted input), each insertion takes O(n) time for n elements

⚠ Quadratic Growth

Space Complexity

O(n)

Tree nodes storage plus recursion stack for depth calculation

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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

Build Tree and Measure Depth — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler