LeetCode 1902 - Depth of BST Given Insertion Order

LeetCode Problem 1902

Difficulty: 🟡 Medium
Topics: Array, Tree, Binary Search Tree, Binary Tree, Ordered Set

Solution

Problem Understanding

The problem gives us an array order that represents the exact sequence in which values are inserted into a binary search tree, usually abbreviated as BST. The array is a permutation of integers from 1 to n, which means every value appears exactly once and there are no duplicates.

We are asked to determine the depth of the resulting BST after all insertions are complete.

A binary search tree follows two important rules:

Every node in the left subtree must contain a smaller value than the current node.
Every node in the right subtree must contain a larger value than the current node.

Insertion into a BST is performed by starting at the root and repeatedly moving left or right depending on whether the new value is smaller or larger than the current node.

The depth of the tree is defined as the number of nodes on the longest path from the root to any leaf node. A tree containing only one node has depth 1.

For example, if the insertion order is:

[2,1,4,3]

The BST becomes:

The longest path is:

2 -> 4 -> 3

which contains 3 nodes, so the answer is 3.

The constraints are important:

n can be as large as 100000
A naive BST construction can become extremely slow in the worst case
We therefore need an algorithm close to O(n log n)

The input guarantees:

All values are unique
Values range from 1 to n
The order is a valid permutation

These guarantees simplify the implementation because we never need to handle duplicates.

Important edge cases include completely increasing sequences, completely decreasing sequences, and balanced insertion patterns. Increasing or decreasing orders create highly skewed trees and can expose inefficient implementations.

Approaches

Brute Force Approach

The most direct solution is to actually build the binary search tree.

For every value in order:

Start at the root.
Compare the current value with the node value.
Move left or right depending on the comparison.
Continue until an empty child position is found.
Insert the new node there.
Track the depth reached during insertion.

This produces the correct answer because it exactly simulates BST insertion.

However, this approach can become extremely slow.

Consider:

[1,2,3,4,5,...]

The BST becomes a linked list:

Each insertion traverses almost the entire tree.

The total complexity becomes:

1 + 2 + 3 + ... + n = O(n²)

With n = 100000, this is too slow.

Optimal Approach

The key insight is that we do not need to explicitly build the tree.

When inserting a new value into a BST, its parent must be either:

The closest smaller inserted value
The closest larger inserted value

Among these two candidates, whichever was inserted later becomes the parent.

We can process values in insertion order while maintaining:

A sorted set of inserted values
The depth of each inserted value

For each new value:

Find its predecessor in sorted order.
Find its successor in sorted order.
The new node depth is:

max(depth(predecessor), depth(successor)) + 1

This works because the insertion path always ends beneath the deeper valid neighbor.

To efficiently find predecessors and successors, we use a sorted structure with binary search.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Explicit BST construction can degenerate into a chain
Optimal	O(n log n)	O(n)	Uses ordered insertion and neighbor depth tracking

Algorithm Walkthrough

Initialize a sorted list containing the first inserted value, because the first element always becomes the root.
Store the depth of the root as 1 in a hash map. The hash map allows constant-time retrieval of previously computed depths.
Initialize the answer as 1, since the root alone gives depth 1.
For each subsequent value in order, use binary search to find the position where it would be inserted into the sorted list.
The value immediately to the left of this position is the predecessor, which is the closest smaller inserted value.
The value immediately to the right of this position is the successor, which is the closest larger inserted value.
Retrieve the depths of the predecessor and successor if they exist.
The new node depth becomes:

max(left_depth, right_depth) + 1

This works because the insertion path must terminate beneath whichever neighboring node is deeper.

Store the computed depth in the hash map.
Insert the value into the sorted list so future insertions can locate it as a neighbor.
Update the global maximum depth.
After processing all values, return the maximum depth found.

Why it works

For every inserted value, the BST insertion path is uniquely determined by already inserted values. The new node must become a child of either its nearest smaller ancestor or nearest larger ancestor. Among these two candidates, the deeper node determines the actual insertion location. Therefore, taking the maximum neighbor depth and adding one correctly computes the depth of the new node.

Python Solution

from bisect import bisect_left
from typing import List

class Solution:
    def maxDepthBST(self, order: List[int]) -> int:
        sorted_values = [order[0]]
        depth = {order[0]: 1}

        max_depth = 1

        for value in order[1:]:
            index = bisect_left(sorted_values, value)

            left_depth = 0
            right_depth = 0

            if index > 0:
                predecessor = sorted_values[index - 1]
                left_depth = depth[predecessor]

            if index < len(sorted_values):
                successor = sorted_values[index]
                right_depth = depth[successor]

            current_depth = max(left_depth, right_depth) + 1

            depth[value] = current_depth
            max_depth = max(max_depth, current_depth)

            sorted_values.insert(index, value)

        return max_depth

The implementation begins by initializing the root node. Since the first inserted value always becomes the root, its depth is immediately known to be 1.

The sorted_values list stores all inserted elements in sorted order. This structure allows binary search through bisect_left, which efficiently locates predecessor and successor candidates.

The depth dictionary maps each inserted value to its computed depth. Once a node depth is known, it never changes.

For every new value, we locate its insertion position in the sorted list. The neighbor on the left is the predecessor and the neighbor on the right is the successor.

The node depth is computed as:

max(predecessor_depth, successor_depth) + 1

Finally, we insert the value into the sorted list and update the global maximum depth.

Go Solution

package main

import "sort"

func maxDepthBST(order []int) int {
	sortedValues := []int{order[0]}
	depth := map[int]int{
		order[0]: 1,
	}

	maxDepth := 1

	for i := 1; i < len(order); i++ {
		value := order[i]

		index := sort.SearchInts(sortedValues, value)

		leftDepth := 0
		rightDepth := 0

		if index > 0 {
			predecessor := sortedValues[index-1]
			leftDepth = depth[predecessor]
		}

		if index < len(sortedValues) {
			successor := sortedValues[index]
			rightDepth = depth[successor]
		}

		currentDepth := max(leftDepth, rightDepth) + 1

		depth[value] = currentDepth

		if currentDepth > maxDepth {
			maxDepth = currentDepth
		}

		sortedValues = append(sortedValues, 0)
		copy(sortedValues[index+1:], sortedValues[index:])
		sortedValues[index] = value
	}

	return maxDepth
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python solution.

The main difference is that Go does not provide a built-in ordered list insertion utility like Python's insert. We manually expand the slice and shift elements using copy.

The sort.SearchInts function performs binary search to locate the insertion position efficiently.

Since all values fit comfortably within standard integer ranges, overflow is not a concern.

Worked Examples

Example 1

Input:

order = [2,1,4,3]

Initial state:

Step	Sorted Values	Depth Map	Max Depth
Start	[2]	{2:1}	1

Insert 1:

Predecessor does not exist
Successor is 2
Depth = 1 + 1 = 2

Step	Sorted Values	Depth Map	Max Depth
After 1	[1,2]	{2:1, 1:2}	2

Insert 4:

Predecessor is 2
Successor does not exist
Depth = 1 + 1 = 2

Step	Sorted Values	Depth Map	Max Depth
After 4	[1,2,4]	{2:1,1:2,4:2}	2

Insert 3:

Predecessor is 2
Successor is 4
Depth = max(1,2) + 1 = 3

Step	Sorted Values	Depth Map	Max Depth
After 3	[1,2,3,4]	{2:1,1:2,4:2,3:3}	3

Final answer:

Example 2

Input:

order = [2,1,3,4]

Inserted	Predecessor	Successor	Computed Depth
2	None	None	1
1	None	2	2
3	2	None	2
4	3	None	3

Final answer:

Example 3

Input:

order = [1,2,3,4]

Inserted	Predecessor	Successor	Computed Depth
1	None	None	1
2	1	None	2
3	2	None	3
4	3	None	4

The BST becomes completely skewed.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Python list insertion shifts elements
Space	O(n)	Depth map and sorted storage

Although predecessor and successor lookup uses binary search in O(log n), inserting into a Python list requires shifting elements, which costs O(n) in the worst case.

In interview settings, this solution is often accepted because the conceptual optimization focuses on neighbor-based depth computation. A truly optimal implementation would require a balanced ordered set structure such as a TreeMap, Treap, AVL tree, or Red-Black tree to achieve full O(n log n) performance.

Test Cases

solution = Solution()

assert solution.maxDepthBST([2, 1, 4, 3]) == 3  # balanced with one deeper branch
assert solution.maxDepthBST([2, 1, 3, 4]) == 3  # right subtree extension
assert solution.maxDepthBST([1, 2, 3, 4]) == 4  # completely increasing order
assert solution.maxDepthBST([4, 3, 2, 1]) == 4  # completely decreasing order
assert solution.maxDepthBST([3]) == 1  # single node tree
assert solution.maxDepthBST([3, 1, 5, 2, 4]) == 3  # relatively balanced tree
assert solution.maxDepthBST([5, 2, 8, 1, 3, 7, 9]) == 3  # nearly perfect BST
assert solution.maxDepthBST([5, 1, 2, 3, 4]) == 5  # long skewed subtree
assert solution.maxDepthBST([2, 3, 1]) == 2  # minimal balanced structure
assert solution.maxDepthBST([7, 3, 1, 2, 5, 4, 6]) == 4  # mixed insertion order

Test	Why
`[2,1,4,3]`	Validates mixed left and right insertions
`[2,1,3,4]`	Tests right-side chain growth
`[1,2,3,4]`	Tests worst-case increasing skew
`[4,3,2,1]`	Tests worst-case decreasing skew
`[3]`	Validates smallest possible input
`[3,1,5,2,4]`	Tests balanced insertion behavior
`[5,2,8,1,3,7,9]`	Tests near-perfect BST formation
`[5,1,2,3,4]`	Tests deep left-rooted skew
`[2,3,1]`	Tests simple balanced tree
`[7,3,1,2,5,4,6]`	Tests irregular insertion structure

Edge Cases

Completely Increasing Input

An input such as:

[1,2,3,4,5]

creates a BST where every node becomes the right child of the previous node. This is the worst possible BST shape and produces maximum depth equal to n.

Naive implementations often become quadratic because every insertion traverses the entire tree. Our implementation correctly computes depths using predecessor relationships without explicitly traversing the tree.

Completely Decreasing Input

An input such as:

[5,4,3,2,1]

creates a fully left-skewed tree.

This case is symmetric to the increasing-order case and can expose bugs where predecessor or successor handling assumes one side always exists. Our implementation safely checks boundaries before accessing neighbors.

Single Element Input

When the array contains only one value:

[3]

the BST contains only the root node.

A common mistake is returning depth 0 instead of 1. Our implementation initializes the root depth correctly as 1, ensuring the correct answer is returned immediately.