Solution Explanation

This problem asks to find the maximum depth of a Binary Search Tree (BST) given the insertion order of nodes. A naive approach would involve constructing the BST and then traversing it to find the depth. However, this would result in O(N^2) time complexity in the worst case (a skewed tree). The optimal solution leverages the properties of a BST and utilizes a SortedDict (Python) or TreeMap (Java) to efficiently track the depth of each node.

Core Idea:

The depth of a node in a BST is 1 plus the maximum depth of its left and right subtrees. Instead of explicitly building the tree, we can infer the depth of a node based on its position within the sorted insertion order. The SortedDict (or TreeMap) stores nodes and their depths, enabling efficient lookups of the nearest smaller and larger nodes to determine the depth of a newly inserted node.

Algorithm:

1. Initialization: Create a sorted dictionary/map. Add sentinel keys 0 and infinity with depth 0 to handle boundary cases during lookups. Insert the first element from order with depth 1.

2. Iteration: Iterate through the remaining elements in order. For each element v:

   • Find the largest key smaller than v (lower) and the smallest key larger than v (higher) in the sorted dictionary/map using efficient binary search.
   • The depth of v is 1 + max(depth(lower), depth(higher)).
   • Update the dictionary/map with v and its calculated depth.
   • Track the maximum depth encountered so far.

3. Return: Return the maximum depth.

Time Complexity Analysis:

The dominant operation is the insertion and lookups in the SortedDict/TreeMap. Both operations take O(log N) time on average, where N is the number of nodes. Since we iterate through N nodes, the overall time complexity is O(N log N).

Space Complexity Analysis:

The SortedDict/TreeMap stores at most N nodes and their associated depths. Therefore, the space complexity is O(N).

Code Explanation (Python):

class Solution:
    def maxDepthBST(self, order: List[int]) -> int:
        sd = SortedDict({0: 0, inf: 0, order[0]: 1}) # SortedDict from the `sortedcontainers` library
        ans = 1
        for v in order[1:]:
            lower = sd.bisect_left(v) - 1 #Find index of the largest key smaller than v
            higher = lower + 1            #Find index of the smallest key larger than v
            depth = 1 + max(sd.values()[lower], sd.values()[higher]) #Calculate depth
            ans = max(ans, depth)        #Update max depth
            sd[v] = depth                #Insert the new node and depth
        return ans

Code Explanation (Java):

class Solution {
    public int maxDepthBST(int[] order) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        tm.put(0, 0);
        tm.put(Integer.MAX_VALUE, 0);
        tm.put(order[0], 1);
        int ans = 1;
        for (int i = 1; i < order.length; ++i) {
            int v = order[i];
            Map.Entry<Integer, Integer> lower = tm.lowerEntry(v); //Find the largest key smaller than v
            Map.Entry<Integer, Integer> higher = tm.higherEntry(v); //Find the smallest key larger than v
            int depth = 1 + Math.max(lower.getValue(), higher.getValue()); //Calculate depth
            ans = Math.max(ans, depth); //Update max depth
            tm.put(v, depth); //Insert new node and depth
        }
        return ans;
    }
}

Remember to install the sortedcontainers library for Python if you use the Python solution (pip install sortedcontainers). The Java solution uses the built-in TreeMap. Both leverage the efficient logarithmic time operations of these data structures to achieve the optimal time complexity.