Back to all solutions

#1902 - Depth of BST Given Insertion Order

Problem Description

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.

Solution

/**
 * @param {number[]} order
 * @return {number}
 */
var maxDepthBST = function(order) {
  const n = order.length;
  const parents = new Array(n + 1).fill(0);
  const insertOrders = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    insertOrders[order[i]] = i + 1;
  }

  const stack = [];

  for (let node = 0; node <= n; node++) {
    const insertOrder = insertOrders[node];

    while (stack.length > 0 && insertOrders[stack[stack.length - 1]] > insertOrder) {
      const prevNode = stack.pop();
      if (insertOrders[parents[prevNode]] < insertOrder) {
        parents[prevNode] = node;
      }
    }

    if (stack.length > 0) {
      parents[node] = stack[stack.length - 1];
    }

    stack.push(node);
  }

  const depths = new Array(n + 1).fill(0);
  for (const num of order) {
    depths[num] = depths[parents[num]] + 1;
  }

  return Math.max(...depths);
};