Depth of BST Given Insertion Order

medium tree bst ordered set binary search

Problem

You are given a permutation of distinct values. Insert them one by one into an initially empty binary search tree (BST) in the given order: each new value walks down from the root, going left when it is smaller and right when it is larger, until it lands on an empty spot. Return the maximum depth the tree reaches (the root is at depth 1).

Inputorder = [4, 2, 3, 1, 5, 6]

Output3

4 is the root (depth 1). 2 and 5 attach at depth 2. 3, 1 and 6 attach at depth 3. The deepest node sits at depth 3.

insertion order (distinct values, comma separated)

class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def max_depth_bst(order):
    root = None
    best = 0
    for x in order:
        if root is None:
            root = Node(x)
            best = max(best, 1)
            continue
        node, depth = root, 1
        while True:
            depth += 1
            if x < node.val:
                if node.left is None:
                    node.left = Node(x)
                    break
                node = node.left
            else:
                if node.right is None:
                    node.right = Node(x)
                    break
                node = node.right
        best = max(best, depth)
    return best

function maxDepthBST(order) {
  let root = null, best = 0;
  for (const x of order) {
    if (root === null) {
      root = { val: x, left: null, right: null };
      best = Math.max(best, 1);
      continue;
    }
    let node = root, depth = 1;
    while (true) {
      depth++;
      if (x < node.val) {
        if (node.left === null) { node.left = { val: x, left: null, right: null }; break; }
        node = node.left;
      } else {
        if (node.right === null) { node.right = { val: x, left: null, right: null }; break; }
        node = node.right;
      }
    }
    best = Math.max(best, depth);
  }
  return best;
}

class Solution {
    static class Node { int val; Node left, right; Node(int v) { val = v; } }
    public int maxDepthBST(int[] order) {
        Node root = null;
        int best = 0;
        for (int x : order) {
            if (root == null) {
                root = new Node(x);
                best = Math.max(best, 1);
                continue;
            }
            Node node = root;
            int depth = 1;
            while (true) {
                depth++;
                if (x < node.val) {
                    if (node.left == null) { node.left = new Node(x); break; }
                    node = node.left;
                } else {
                    if (node.right == null) { node.right = new Node(x); break; }
                    node = node.right;
                }
            }
            best = Math.max(best, depth);
        }
        return best;
    }
}

struct Node { int val; Node *left = nullptr, *right = nullptr; Node(int v) : val(v) {} };

int maxDepthBST(vector<int>& order) {
    Node* root = nullptr;
    int best = 0;
    for (int x : order) {
        if (!root) {
            root = new Node(x);
            best = max(best, 1);
            continue;
        }
        Node* node = root;
        int depth = 1;
        while (true) {
            depth++;
            if (x < node->val) {
                if (!node->left) { node->left = new Node(x); break; }
                node = node->left;
            } else {
                if (!node->right) { node->right = new Node(x); break; }
                node = node->right;
            }
        }
        best = max(best, depth);
    }
    return best;
}

Explanation

A binary search tree keeps everything ordered: for any node, smaller values live in its left subtree and larger values live in its right subtree. When we insert a value, we start at the root and walk down, turning left or right by comparing, until we reach an empty slot where the new node hangs.

The depth a node lands at is simply how many comparisons it took to get there. The root sits at depth 1; its children at depth 2; and so on. Because the values arrive in a fixed order, the shape of the tree — and therefore the maximum depth — is fully determined by that order.

So the algorithm is just "simulate the insertions." For each incoming value we descend from the root, incrementing a depth counter at every step, and stop the moment we find a free child pointer. We keep a running best of the largest depth any node reached.

The order matters a lot. A nicely interleaved order keeps the tree shallow and balanced, while a sorted order like [1,2,3,4] degenerates into a straight chain of depth n. This is exactly why self-balancing trees exist — but here we measure the raw, unbalanced result.

Worked example on [4,2,3,1,5,6]: 4 becomes the root (depth 1). 2 < 4 → left child, depth 2. 3 < 4 → left, then 3 > 2 → right of 2, depth 3. 1 goes left of 4 then left of 2, depth 3. 5 > 4 → right, depth 2. 6 > 4 then 6 > 5, depth 3. The maximum depth observed is 3.

Time: O(n · h) (worst case O(n²)) Space: O(n)