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
class Solution {
 public:
  int maxDepthBST(vector<int>& order) {
    int ans = 1;
    map<int, int> valToDepth;

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

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int maxDepthBST(int[] order) {
    int ans = 1;
    TreeMap<Integer, Integer> valToDepth = new TreeMap<>();

    for (final int val : order) {
      Map.Entry<Integer, Integer> l = valToDepth.floorEntry(val);
      Map.Entry<Integer, Integer> r = valToDepth.ceilingEntry(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);
      valToDepth.put(val, depth);
    }

    return ans;
  }
}