How recursion actually works

[josh yen]

This question is:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

One example is with this input array, [-10,-3,0,5,9]   , a valid tree would be    
      0
    /   \
  -10  5
     \    \
    -3.   9

This is the code that solves this problem:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.empty())
            return nullptr;
        return buildTree(nums, 0, nums.size() - 1);
    }
    
    TreeNode* buildTree(vector<int>& nums, int left, int right)
    {
        if(left > right)
            return nullptr;
        int mid = left + (right - left)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = buildTree(nums, left, mid - 1);
        root->right = buildTree(nums, mid+1, right);
        return root;        
    }
};

I am confused how this exactly works. The output with the above example is [0,-10,5,null,-3,null,9].

I am confused on what each step of recursion does here and when left would ever be greater than right? Could someone walk through the steps on what the left, right, and midpoint would be at each step of this function? I am confused at which points the right recursive call is used after the left.

I haven't been able to fully understand recursion and this would help a ton!
Thank you so much any help is appreciated.

[Stephan van Hulst]

buildTree() takes a subrange of a vector and splits it in three parts: A middle element, and the elements left of the middle and the elements right of the middle.

The middle element is used to create the root of the tree, and the left elements and right elements are used to create the left and right subtrees respectively.

At some point, you can no longer split the vector up in three parts anymore, right? For instance, what happens when the subrange of the vector only contains one element?

For instance, let's say that left is 4 and right is also 4. This corresponds to the sub-vector [9]. The mid variable will then be 4 + (4 - 4) / 2 which evaluates to 4. So the root of the corresponding subtree is nums[4], or 9. Here are how the subtrees of the subtree with root 9 are built:
rootNineTree->left  = buildTree(nums, 4,   4-1 ); rootNineTree->right = buildTree(nums, 4+1, 4   );
In both subtrees, left > right. That means that the subtree with root 9 looks like this:

    9
   / \
null null