Median in a BST

The idea that root is the middle element gets you a “balanced” bst.

TreeNode* sortedArrayToBST(vector<int>& nums) {
    int n = nums.size();
 
    auto f = [&](auto&& f, int l, int r) -> TreeNode* {
        if (l > r)
            return nullptr;
        int mid = (l + r) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = f(f, l, mid - 1);
        root->right = f(f, mid + 1, r);
        return root;
    };
    return f(f, 0, n - 1);
}