1902. Depth of BST Given Insertion Order

You are given a 0-indexed integer array order of length n, a permutation of integers from 1 to n representing the order of insertion into a binary search tree.

A binary search tree is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

The binary search tree is constructed as follows:

• order[0] will be the root of the binary search tree.
• All subsequent elements are inserted as the child of any existing node such that the binary search tree properties hold.

Return the depth of the binary search tree.

A binary tree’s depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

class Solution {
public:
    int maxDepthBST(vector<int>& order) {
        map<int, int> mp;
        mp[0] = 0;
        int res = 0;
        for(auto& o : order) {
            auto it = prev(mp.upper_bound(o));
            res = max(res, mp[o] = ++it->second);
        }
        return res;
    }
};