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 binary search tree is constructed as follows:
order[0] will be the root of the binary search tree.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.length1 <= n <= 105order is a permutation of integers between 1 and n.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).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct BST Simulation | O(n²) | O(n) | Useful for understanding how BST insertion works or when constraints are very small |
| Ordered Set with Predecessor/Successor Depth | O(n log n) | O(n) | Best general solution; efficient for large arrays using TreeMap or balanced BST |
Depth of BST given insertion order | Leetcode 1902 • Debstuti Das • 86 views views
Watch 1 more video solutions →Practice Depth of BST Given Insertion Order with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor