• Justification:
  • The maximum value is 9, which becomes the root.
  • Left subarray [7, 2, 5, 3] builds the left subtree:
    • Maximum is 7.
    • Right subarray [2, 5, 3] builds further:
      • Maximum is 5 with left child 2 and right child 3.
  • Right subarray [1] becomes the right child.

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• All integers in nums are unique.

Solution

To construct the Maximum Binary Tree from the given array of unique integers, we employ a Divide and Conquer strategy. This approach systematically breaks down the problem into smaller, more manageable subproblems, ensuring that each segment of the array is processed efficiently.

Divide:

• Identify the Maximum: For any given subarray, we first locate the maximum value. This value becomes the root of the current subtree.
• Divide the Array: Once the maximum is identified, the array is divided into two parts:
  • Left Subarray: Elements to the left of the maximum value.
  • Right Subarray: Elements to the right of the maximum value.

Conquer:

• Recursive Construction: We recursively apply the same process to the left and right subarrays to construct the left and right subtrees, respectively.
• Base Case: If a subarray is empty (i.e., the start index equals the end index), we return null, indicating no further nodes to add.

This divide and conquer approach is effective because it ensures that each subtree is constructed optimally by always selecting the maximum available value as the root, thereby maintaining the properties of the Maximum Binary Tree. Additionally, by recursively handling smaller subarrays, the algorithm efficiently builds the entire tree with clear parent-child relationships.

Step-by-Step Algorithm

• Recursive Tree Construction:

  • Check for Base Case:
    • If start is equal to end, return null to handle an empty array.
  • Identify the Maximum Element:
    • Call findIndexOfMaximum(nums, start, end) to find the index of the largest number in the current subarray.
      • The maximum value becomes the root of the current subtree, ensuring the tree adheres to the Maximum Binary Tree properties.
  • Create the Root Node:
    • Instantiate a new TreeNode with the value nums[maxIndex].
      • This steps establishes the root of the subtree based on the identified maximum value.
  • Construct the Left Subtree:
    • Recursively call buildTree(nums, start, maxIndex) and assign the result to root.left.
      • This step builds the left subtree using elements to the left of the maximum value, maintaining the tree structure.
  • Construct the Right Subtree:
    • Recursively call buildTree(nums, maxIndex + 1, end) and assign the result to root.right.
      • This step builds the right subtree using elements to the right of the maximum value, ensuring all elements are included in the tree.
  • Return the Root Node:
    • After assigning both left and right children, return the root node.

• Find the Index of the Maximum Value:

  • In the findIndexOfMaximum method:
    • Initialize maxIndex to start.
      • Here, we assume that the first element of the subarray is the maximum initially.
    • Iterate from start to end - 1:
      • For each index i, if nums[i] > nums[maxIndex], update maxIndex to i.
        • This step identifies the true maximum value in the subarray by comparison.
    • Return maxIndex.
      • This step provides the position of the maximum value to determine the root of the subtree.

Algorithm Walkthrough

Let's demonstrate the algorithm using Example 1:

Example 1:

• Input: nums = [4, 3, 1, 7, 0, 5]
• Expected Output: [7, 4, 5, null, 3, 0, null, null, 1]

1. Start with the Entire Array:

   • Call buildMaximumBinaryTree(nums), which invokes buildTree(nums, 0, 6) for the full array [4, 3, 1, 7, 0, 5].

2. First Recursive Call (Root Node):

   • Subarray: [4, 3, 1, 7, 0, 5]
   • Maximum Value: 7 at index 3. Create TreeNode(7).
   • Recursive Calls:
     • Left Subtree: Call buildTree(nums, 0, 3) for [4, 3, 1].
     • Right Subtree: Call buildTree(nums, 4, 6) for [0, 5].

3. Second Recursive Call (Left Subtree of 7):

   • Subarray: [4, 3, 1]
   • Maximum Value: 4 at index 0. Create TreeNode(4).
   • Recursive Calls:
     • Left Subtree: Call buildTree(nums, 0, 0) for an empty subarray (returns null).
     • Right Subtree: Call buildTree(nums, 1, 3) for [3, 1].

4. Third Recursive Call (Right Subtree of 4):

   • Subarray: [3, 1]
   • Maximum Value: 3 at index 1. Create TreeNode(3).
   • Recursive Calls:
     • Left Subtree: Call buildTree(nums, 1, 1) for an empty subarray (returns null).
     • Right Subtree: Call buildTree(nums, 2, 3) for [1].

5. Fourth Recursive Call (Right Subtree of 3):

   • Subarray: [1]
   • Maximum Value: 1 at index 2. Create TreeNode(1).
   • Recursive Calls:
     • Left Subtree: Call buildTree(nums, 2, 2) for an empty subarray (returns null).
     • Right Subtree: Call buildTree(nums, 3, 3) for an empty subarray (returns null).

6. Second Recursive Call Returns:

   • TreeNode(4) is completed with:
     • Left child: null
     • Right child: TreeNode(3) → TreeNode(3).right = TreeNode(1)

7. First Recursive Call Proceeds to Right Subtree of 7:

   • Subarray: [0, 5]
   • Maximum Value: 5 at index 5. Create TreeNode(5).
   • Recursive Calls:
     • Left Subtree: Call buildTree(nums, 4, 5) for [0].
     • Right Subtree: Call buildTree(nums, 6, 6) for an empty subarray (returns null).

8. Third Recursive Call (Left Subtree of 5):

   • Subarray: [0]
   • Maximum Value: 0 at index 4. Create TreeNode(0).
   • Recursive Calls:
     • Left Subtree: Call buildTree(nums, 4, 4) for an empty subarray (returns null).
     • Right Subtree: Call buildTree(nums, 5, 5) for an empty subarray (returns null).

9. First Recursive Call Completes:

   • TreeNode(7) is completed with:
     • Left child: TreeNode(4) → TreeNode(4).right = TreeNode(3) → TreeNode(3).right = TreeNode(1)
     • Right child: TreeNode(5) → TreeNode(5).left = TreeNode(0)

Code