Problem Description

You need to construct a binary search tree (BST) by inserting elements one by one from a given array order, then find the maximum depth of the resulting tree.

The array order is a permutation of integers from 1 to n, representing the sequence in which values are inserted into the BST. The first element order[0] becomes the root of the tree. Each subsequent element is inserted following standard BST insertion rules:

• If the value is less than the current node, go to the left subtree
• If the value is greater than the current node, go to the right subtree
• Continue this process until finding an empty position, then insert the node there

The depth of the BST is the number of nodes along the longest path from the root to any leaf node.

For example, if order = [2, 1, 4, 3]:

1. Insert 2 as the root (depth 1)
2. Insert 1 as left child of 2 (depth 2)
3. Insert 4 as right child of 2 (depth 2)
4. Insert 3 as left child of 4 (depth 3)

The resulting tree has a maximum depth of 3.

The solution uses a SortedDict to efficiently track the depth of each inserted node. For each new value, it finds the closest smaller and larger values already in the tree. The new node will be a child of one of these adjacent nodes, specifically the one with greater depth. The depth of the new node is one more than its parent's depth. The algorithm maintains the maximum depth seen throughout all insertions.

Intuition

When inserting a new value into a BST, we need to find where it will be placed. The key insight is that a new node will always become a leaf node - it never gets inserted between existing nodes. This new leaf will be a child of some existing node.

But which existing node will be the parent? When we traverse the BST to insert value v, we compare it with nodes along a path from root to a leaf. The last node we visit before reaching an empty spot becomes the parent. This parent node will be either:

1. The largest value smaller than v (if v becomes its right child)
2. The smallest value larger than v (if v becomes its left child)

Here's the crucial observation: between these two adjacent values (the closest smaller and larger values), the new node v will be attached to whichever one was inserted later (has greater depth). Why? Because if the smaller value has greater depth, it means we reached it by going through the larger value first, so v becomes the right child of the smaller value. Conversely, if the larger value has greater depth, we reached it through the smaller value, so v becomes the left child of the larger value.

This means we don't need to build the actual tree structure. We only need to:

1. Keep track of all inserted values and their depths
2. For each new value, find its immediate neighbors (closest smaller and larger values)
3. The new value's depth is 1 + max(depth of smaller neighbor, depth of larger neighbor)

A SortedDict is perfect for this because it maintains values in sorted order and allows efficient binary search to find neighbors. We initialize it with sentinel values 0 and inf at depth 0 to handle edge cases when inserting the minimum or maximum values.

Learn more about Tree, Binary Search Tree and Binary Tree patterns.

Solution Approach

The solution uses a SortedDict data structure to efficiently track inserted values and their corresponding depths without building the actual BST.

Initialization:

sd = SortedDict({0: 0, inf: 0, order[0]: 1})

• We initialize the SortedDict with sentinel values: 0 and inf both at depth 0
• These sentinels handle edge cases when inserting minimum or maximum values
• The root node order[0] is inserted with depth 1
• Variable ans tracks the maximum depth seen so far, initially 1

Main Algorithm: For each subsequent value v in order[1:]:

1. Find the closest neighbors:

   lower = sd.bisect_left(v) - 1
   higher = lower + 1

   • bisect_left(v) returns the index where v would be inserted to maintain sorted order
   • lower is the index of the largest value smaller than v
   • higher is the index of the smallest value larger than v

2. Calculate the depth of the new node:

   depth = 1 + max(sd.values()[lower], sd.values()[higher])

   • The new node will be a child of either the lower or higher neighbor
   • It attaches to whichever neighbor has greater depth (was inserted more recently in that subtree)
   • The new node's depth is one more than its parent's depth

3. Update the maximum depth and insert the new node:

   ans = max(ans, depth)
   sd[v] = depth

   • Update ans if we found a deeper node
   • Add the new value and its depth to the SortedDict

Time Complexity: O(n log n) where n is the length of the order array. Each insertion into the SortedDict takes O(log n) time.

Space Complexity: O(n) for storing all values and their depths in the SortedDict.

Example Walkthrough

Let's trace through the algorithm with order = [3, 1, 2, 5, 4, 6].

Initial Setup:

• SortedDict: {0: 0, inf: 0, 3: 1}
• Root node 3 has depth 1
• ans = 1

Insert 1:

• Find neighbors of 1: lower = 0 (depth 0), higher = 3 (depth 1)
• Depth of 1 = 1 + max(0, 1) = 2
• Node 1 becomes left child of 3
• SortedDict: {0: 0, 1: 2, 3: 1, inf: 0}
• ans = 2

Insert 2:

• Find neighbors of 2: lower = 1 (depth 2), higher = 3 (depth 1)
• Depth of 2 = 1 + max(2, 1) = 3
• Node 2 becomes right child of 1
• SortedDict: {0: 0, 1: 2, 2: 3, 3: 1, inf: 0}
• ans = 3

Insert 5:

• Find neighbors of 5: lower = 3 (depth 1), higher = inf (depth 0)
• Depth of 5 = 1 + max(1, 0) = 2
• Node 5 becomes right child of 3
• SortedDict: {0: 0, 1: 2, 2: 3, 3: 1, 5: 2, inf: 0}
• ans = 3

Insert 4:

• Find neighbors of 4: lower = 3 (depth 1), higher = 5 (depth 2)
• Depth of 4 = 1 + max(1, 2) = 3
• Node 4 becomes left child of 5
• SortedDict: {0: 0, 1: 2, 2: 3, 3: 1, 4: 3, 5: 2, inf: 0}
• ans = 3

Insert 6:

• Find neighbors of 6: lower = 5 (depth 2), higher = inf (depth 0)
• Depth of 6 = 1 + max(2, 0) = 3
• Node 6 becomes right child of 5
• SortedDict: {0: 0, 1: 2, 2: 3, 3: 1, 4: 3, 5: 2, 6: 3, inf: 0}
• ans = 3

The resulting BST structure:

       3 (depth 1)
      / \
     1   5 (depth 2)
      \  / \
      2 4   6 (depth 3)

Maximum depth = 3

The key insight: when inserting value 4, it finds neighbors 3 and 5. Since 5 has greater depth (2) than 3 (1), node 4 attaches to node 5 as its child. This happens because to reach position 4 in the actual BST, we must traverse through node 5, making 5 the parent of 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the input array order.

• The code iterates through the array once with a for loop that runs n-1 times
• Inside each iteration:
  • sd.bisect_left(v) performs a binary search operation on the sorted dictionary, which takes O(log k) where k is the current size of the dictionary (at most n+2 elements)
  • sd.values()[lower] and sd.values()[higher] access values by index, which in a SortedDict takes O(log k) time each
  • Inserting a new key-value pair with sd[v] = depth takes O(log k) time to maintain the sorted order
• Since we perform these operations for each element and the dictionary grows to size O(n), the total time complexity is O(n log n)

Space Complexity: O(n) where n is the length of the input array order.

• The SortedDict sd stores at most n+2 key-value pairs (all elements from the input array plus the two sentinel values 0 and inf)
• The variable ans and other local variables use O(1) space
• Therefore, the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Assuming the Parent Node

Pitfall: A common mistake is thinking that the new node's parent is simply the node with the value closest to it (minimum absolute difference). This would lead to incorrect depth calculations.

Why it's wrong: In a BST, when inserting a new value, its parent is determined by the path taken during insertion, not just proximity. The parent must be either:

• The largest value smaller than the new value (if the new node becomes its right child)
• The smallest value larger than the new value (if the new node becomes its left child)

Correct approach: The parent is the one among these two candidates that was inserted more recently into that position (has greater depth).

2. Forgetting the Sentinel Values

Pitfall: Omitting the sentinel values 0 and inf from the initial SortedDict setup:

# Incorrect initialization
sorted_dict = SortedDict({order[0]: 1})

Why it fails: Without sentinels, when inserting extreme values:

• If inserting a value smaller than all existing values, lower_index would be -1
• If inserting a value larger than all existing values, higher_index would exceed the valid range
• This causes IndexError when accessing sorted_dict.values()[lower_index] or sorted_dict.values()[higher_index]

Solution: Always initialize with sentinels:

sorted_dict = SortedDict({0: 0, inf: 0, order[0]: 1})

3. Using Regular Dictionary Instead of SortedDict

Pitfall: Attempting to use a regular Python dict and manually finding neighbors:

# Incorrect approach
depths = {order[0]: 1}
for value in order[1:]:
    # Finding neighbors in O(n) time
    smaller = [k for k in depths if k < value]
    larger = [k for k in depths if k > value]
    # ... rest of logic

Why it's inefficient: This approach has O(n²) time complexity because finding neighbors requires scanning all existing keys for each insertion.

Solution: Use SortedDict which maintains keys in sorted order and provides O(log n) bisect operations.

4. Misunderstanding the Depth Calculation

Pitfall: Setting the new node's depth equal to its parent's depth instead of adding 1:

# Incorrect
depth = max(sorted_dict.values()[lower_index], 
           sorted_dict.values()[higher_index])

Correct version:

depth = 1 + max(sorted_dict.values()[lower_index], 
               sorted_dict.values()[higher_index])

The new node is one level deeper than its parent in the tree structure.