Problem statement

https://leetcode.com/problems/depth-of-bst-given-insertion-order/

Solution

The idea is to keep SortedList object with tuples (num, depth). Imagine, that order = [3,1,2,4,5], then we have steps:

  1. [(3, 1)]
  2. [(1, 2), (3, 1)]
  3. [(1, 2), (2, 3), (3, 1)]
  4. [(1, 2), (2, 3), (3, 1), (4, 2)]
  5. [(1, 2), (2, 3), (3, 1), (4, 2), (5, 3)]

On each step we look at left closest and right closest element, choose maximum among them and add 1.

Complexity

Time complexity is O(n log n), space is O(n).

Code

from sortedcontainers import SortedList

class Solution:
    def maxDepthBST(self, order):
        SList, ans = SortedList(), 1
        ans = 1
        
        for num in order:
            ind = SList.bisect((num, 0))
            d = 0
            if ind > 0: d = max(d, SList[ind-1][1])
            if ind < len(SList): d = max(d, SList[ind][1])
            SList.add((num, d + 1))
            ans = max(ans, d + 1)
        
        return ans

Remark

I think it can be solved with segment tree or binary indexed tree as well with the same complexity.