Skip to main content
Talentd

Depth of BST Given Insertion Order - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTreeBinary Search TreeBinary Tree4 min read
Practice this problem

Problem Statement

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 <= 105
  • order is a permutation of integers between 1 and n.

Approach Overview

Problem Overview: You receive an array representing the order in which values are inserted into a Binary Search Tree. Instead of building the full tree explicitly, the goal is to compute the maximum depth the BST reaches after all insertions.

Approach 1: Direct BST Simulation (O(n²) time, O(n) space)

The straightforward way is to build the Binary Search Tree exactly as described. Start with the first value as the root, then insert each next value by walking down the tree and comparing with current nodes until you find the correct position. While inserting, track the depth reached for that node. The maximum depth seen across all insertions is the answer. This approach mirrors how BST insertion works but degrades when the tree becomes skewed. In the worst case (sorted input), each insertion scans almost the entire tree, leading to O(n²) time.

Approach 2: Ordered Set with Neighbor Depth Tracking (O(n log n) time, O(n) space)

The key observation: when inserting a value into a BST, its parent must be either its closest smaller value (predecessor) or closest larger value (successor) among the previously inserted elements. Using an Ordered Set (like TreeMap in Java or a sorted structure in Python), you can quickly locate these neighbors. Store the depth of each inserted value in a hash map.

For every new number x, query the ordered structure to find its predecessor and successor. The depth of x becomes 1 + max(depth[pred], depth[succ]). If one neighbor does not exist, treat its depth as -1 (or 0 depending on indexing). Insert x into the ordered structure and record its depth. Since each lookup and insertion costs O(log n), the overall complexity becomes O(n log n) for n insertions. This avoids building the full Binary Tree structure while still computing correct depths.

Recommended for interviews: The ordered set approach is what interviewers expect. Brute force BST construction shows you understand insertion mechanics, but the neighbor-depth insight demonstrates stronger algorithmic reasoning. Recognizing that only the closest smaller and larger values determine the parent allows you to reduce the complexity from O(n²) to O(n log n).

Solution

Code

PythonJava

Python

Java

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct BST SimulationO(n²)O(n)Useful for understanding how BST insertion works or when constraints are very small
Ordered Set with Predecessor/Successor DepthO(n log n)O(n)Best general solution; efficient for large arrays using TreeMap or balanced BST

Video Solution

Depth of BST given insertion order | Leetcode 1902 • Debstuti Das • 88 views views

Watch 1 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Depth of BST Given Insertion Order with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays