Skip to content

1902. Depth of BST Given Insertion Order 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int maxDepthBST(vector<int>& order) {
    int ans = 1;
    map<int, int> map;  // {val: depth}
    map[order[0]] = 1;

    for (int i = 1; i < order.size(); ++i) {
      const int val = order[i];
      const auto l = map.upper_bound(val);  // min > val
      const auto r = map.lower_bound(val);  // min >= val
      const int leftDepth = l == cbegin(map) ? 0 : prev(l)->second;
      const int rightDepth = r == cend(map) ? 0 : r->second;
      const int depth = max(leftDepth, rightDepth) + 1;
      ans = max(ans, depth);
      map[val] = depth;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int maxDepthBST(int[] order) {
    int ans = 1;
    TreeMap<Integer, Integer> map = new TreeMap<>(); // {val: depth}
    map.put(order[0], 1);

    for (int i = 1; i < order.length; ++i) {
      final int val = order[i];
      Map.Entry<Integer, Integer> l = map.floorEntry(val);   // max <= val
      Map.Entry<Integer, Integer> r = map.ceilingEntry(val); // min >= val
      final int leftDepth = l == null ? 0 : l.getValue();
      final int rightDepth = r == null ? 0 : r.getValue();
      final int depth = Math.max(leftDepth, rightDepth) + 1;
      ans = Math.max(ans, depth);
      map.put(val, depth);
    }

    return ans;
  }
}