How is recursion executed when there are 2 recursive statements like the program below?

Question

I had posted a question earlier however I wasn't clear enough. I am sorry for the confusion but what I meant was if there is a program like :

TreeNode createMinBST(int arr[], int start, int end) {
    if(end< start) return null;

    int mid = (start+end)/2;
    Treenode n= new Treenode(arr[mid]);
    n.left= createMinBST(arr, start, mid-1)  //LINE a
    n.right= createMinBST(arr, mid+1, end);  //LINE b
    return n;
}

How does LINE a and LINE b unroll(like it said in coding interview book) or how does it work? Does LINE a go all the way to the base case and return values and then LINE b executes? Or both the recursive statements go down to the base case simultaneously?

If someone could explain level wise path for creating a Minimal BST from the code given above, it will be really helpful to understand how multiple recursive statements (here 2- Line a and Line b) takes place

Thanks a lot

Answer 1

Looking at your code you're building your tree the same way you'd do a "depth-first search". So you're going deeper (depper left in your case) until there's no more element to process, then you're going back up one level and then again back down.

(btw your 'line A' is missing a semi-colon at the end)

As is often the case when learning or trying to figure out how recursive calls are working, it is convenient to print out the calls.

For example in your case if your starting array contains numbers from [10..24] then your calls may look like this:

Calling minBST on 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24

    Calling minBST (left) on 10, 11, 12, 13, 14, 15, 16

        Calling minBST (left) on 10, 11, 12

            Calling minBST (left) on 10

            Calling minBST (right) on 12

        Calling minBST (right) on 14, 15, 16

            Calling minBST (left) on 14

            Calling minBST (right) on 16

    Calling minBST (right) on 18, 19, 20, 21, 22, 23, 24

        Calling minBST (left) on 18, 19, 20

            Calling minBST (left) on 18

            Calling minBST (right) on 20

        Calling minBST (right) on 22, 23, 24

            Calling minBST (left) on 22

            Calling minBST (right) on 24