How can I walk through this recursive binary tree problem?

Question

This is a working solution of the problem:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return helper(nums, 0, nums.length-1);
    }

    public TreeNode helper(int[] nums, int low, int high){
        if (high < low){ return null; }
        //find max element's index
        int maxIndex = getMaxIndex(nums, low, high);

        //construct root node
        TreeNode root = new TreeNode(nums[maxIndex]);

        //generate left subtree from the left part of subarray
        root.left = helper(nums, low, maxIndex-1);

        //generate right sub tree from the right part of subarray
        root.right = helper(nums, maxIndex+1, high);


        return root; 
    }

    public int getMaxIndex(int[] nums, int low, int high){
        int maxIndex = low;
        for (int i = low+1; i <= high; i++){
            if (nums[i] > nums[maxIndex]){
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

Can someone please walk me through the problem and all of the recursive calls? Right now I do not understand how the solution builds the tree node. I'm currently walking through the problem like this.

1. constructMaximumBinaryTree(int[] nums)

2. int maxIndex = getMaxIndex(nums, 0, 5) so maxIndex = 3.

3. TreeNode root = 6.

4. root.left = helper(nums, 0, 2) so maxIndex = 0.

5. TreeNode root = 3.

6. root.left = helper(nums, 0, -1), which triggers the base case and returns null.

I get lost after step 6. After step 6 returns null, do I move on to root.right = helper(nums, maxIndex+1, high)? If so, what would maxIndex and high be? And what are the next steps?

Answer 1

The short answer is yes, you move to root.right = helper(nums, maxIndex+1, high), where maxIndex = 0 and high = 2, so root.right = helper(nums, 1, 2).

The steps would be:

1. constructMaximumBinaryTree(int[] nums)
2. int maxIndex = getMaxIndex(nums, 0, 5) so maxIndex = 3.
3. TreeNode root = 6.
4. root.left = helper(nums, 0, 2) so maxIndex = 0.
5. TreeNode root = 3.
6. root.left = helper(nums, 0, -1), which triggers the base case and returns null.
7. We proceed with the right subtree for root = 3, so root.right = helper(nums, 1, 2), with maxIndex = 1.
8. TreeNode root = 2.
9. root.left = helper(nums, 1, 0), which triggers the base case and returns null.
10. We proceed with the right subtree for root = 2, so root.right = helper(nums, 2, 2), with maxIndex = 2.
11. TreeNode root = 1.
12. Now both left and right return null, and we return to the right subtree of root = 6.

Answer 2

Typically a recursive approach breaks a problem into multiple sub problems and builds the solution of the original problem by combining their solutions. This is exactly what happens in this case too.

The fact that the definition of maximum tree is itself recursive makes it easier to understand the solution. Note that in steps 2 and 3 of the definition we need to construct a maximum sub tree from a sub array of the original array. Thus we solve the same problem with fewer input elements.

The function helper is the key to this solution - it constructs a maximum tree from a contiguous subarray of the original input array. To understand the solution better first ignore the concrete implementation and assume that it does just that - nums parameter is always the original input array and low and high and the indices of the first and the last element in the sub array respectively (both inclusive). helper returns the root of the maximum tree constructed for the provided sub array. Thus calling help with the whole array will solve the original problem.

Similarly getMaxIndex takes a sub array of the original array (specified the same way) and returns the index of the element in that sub array that has maximum value. According to the definition of maximum tree this would be the index of the root element in the new tree and the index at which we should split the array for the left and right subtrees (point 1 of the definition).

Now if you know that this is what the two functions do it should be relatively easy to understand the logic in them.

Answer 3

I often it find that some well placed print statements can be extremely helpful in understanding the flow of an algorithm, especially when it involves recursion. I've updated your code to print which child , L or R, is being processed and the level, via an indent string.

public TreeNode constructMaximumBinaryTree(int[] nums) {
  return helper(nums, 0, nums.length-1, "", "");
}

public TreeNode helper(int[] nums, int low, int high, String side, String ind){   
  if (high < low){ return null; }

  System.out.println(ind + side + Arrays.toString(Arrays.copyOfRange(nums, low, high+1)));

  //find max element's index
  int maxIndex = getMaxIndex(nums, low, high);

  //construct root node
  TreeNode root = new TreeNode(nums[maxIndex]);

  //generate left subtree from the left part of subarray
  root.left = helper(nums, low, maxIndex-1, "L", ind + "  ");

  //generate right sub tree from the right part of subarray
  root.right = helper(nums, maxIndex+1, high, "R", ind + "  ");

  return root; 
}

On your input this produces:

[3, 2, 1, 6, 0, 5]
  L[3, 2, 1]
    R[2, 1]
      R[1]
  R[0, 5]
    L[0]

Which I think makes the construction of the tree much clearer.