Is Depth of BST Given Insertion Order easy or hard?

Depth of BST Given Insertion Order is considered a Medium difficulty problem. The challenge lies in recognizing that only the nearest smaller and larger inserted values determine the node's parent, enabling an O(n log n) ordered-set solution.

Depth of BST Given Insertion Order Python/Java solution

Python implementations typically simulate an ordered structure using libraries like bisect with sorted lists or external sorted containers. Java solutions commonly use TreeMap or TreeSet to efficiently locate predecessor and successor values while tracking node depths.

How to solve Depth of BST Given Insertion Order in O(n)?

Most standard solutions run in O(n log n) using an ordered set or TreeMap. Achieving true O(n) is difficult because the algorithm must maintain sorted neighbor relationships during insertions. Balanced tree structures naturally introduce a logarithmic factor.

What is the best approach for Depth of BST Given Insertion Order?

The most efficient approach uses an ordered set (such as TreeMap or a balanced BST) to track previously inserted values. For each new number, find its predecessor and successor and compute the depth as 1 + max(depth[pred], depth[succ]). This reduces the complexity to O(n log n) while avoiding explicit tree construction.

Is Depth of BST Given Insertion Order asked at Google/Amazon/Meta?

Depth-based BST construction problems commonly appear in interviews at companies like Google, Amazon, and Meta. They test understanding of BST insertion properties, ordered data structures, and optimization from naive simulation to logarithmic lookup methods.

What data structure is used in Depth of BST Given Insertion Order?

The optimal solution relies on an ordered set or balanced binary search tree structure such as TreeMap, TreeSet, or a sorted container. A hash map is also used to store the computed depth for each inserted value.

What is the time complexity of Depth of BST Given Insertion Order?

The optimal solution runs in O(n log n) time because each insertion performs ordered-set operations like predecessor and successor lookup. A naive BST simulation can degrade to O(n²) in the worst case when the tree becomes completely skewed.

Description Hints 2 Solution Video 21:37

1902. Depth of BST Given Insertion Order

Medium42.5% acceptancePremium elsewhere, free here

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.

Example 1:

Input: order = [2,1,4,3]
Output: 3
Explanation: The binary search tree has a depth of 3 with path 2->3->4.

Example 2:

Input: order = [2,1,3,4]
Output: 3
Explanation: The binary search tree has a depth of 3 with path 2->3->4.

Example 3:

Input: order = [1,2,3,4]
Output: 4
Explanation: The binary search tree has a depth of 4 with path 1->2->3->4.

Constraints:

n == order.length
1 <= n <= 10⁵
order is a permutation of integers between 1 and n.

Topics

Hints open one at a time

Hint 1

There are at most 2 possible places where a new node can be inserted?

Hint 2

How can we keep track of the depth of each node?

21:37

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[2,1,4,3]

Input

[2,1,3,4]

Input

[1,2,3,4]

Your code is saved on this device.Solution