medium Maximum Binary Tree

Problem Statement

Given an integer array nums with no duplicates, construct a maximum binary tree from a given array by following these rules:

• The root of the tree is the highest value in the nums.
• The left subtree is recursively built from the elements to the left of the highest value in subarray prefix.
• The right subtree is recursively built from the elements to the right of the highest value in subarray suffix.

Return the resulting maximum binary tree.

Examples

Example 1:

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

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

Example 2:

• Input: nums = [1, 4, 3, 2]
• Expected Output: [4, 1, 3, null, null, null, 2]

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

Example 3:

• Input: nums = [7, 2, 5, 3, 9, 1]
• Expected Output: [9, 7, 1, null, 5, null, null, 2, 3]

• 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

import java.util.*;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  public TreeNode buildMaximumBinaryTree(int[] nums) {
    return buildTree(nums, 0, nums.length);
  }

  private TreeNode buildTree(int[] nums, int start, int end) {
    // Base case: if the current subarray is empty, return null
    if (start == end) {
      return null;
    }

    // Find the index of the maximum value in the current subarray
    int maxIndex = findIndexOfMaximum(nums, start, end);

    // Create a new TreeNode with the maximum value
    TreeNode root = new TreeNode(nums[maxIndex]);

    // Recursively build the left subtree from the left subarray
    root.left = buildTree(nums, start, maxIndex);

    // Recursively build the right subtree from the right subarray
    root.right = buildTree(nums, maxIndex + 1, end);

    return root;
  }

  private int findIndexOfMaximum(int[] nums, int start, int end) {
    int maxIndex = start;
    // Iterate through the subarray to find the maximum value's index
    for (int i = start; i < end; i++) {
      if (nums[i] > nums[maxIndex]) {
        maxIndex = i;
      }
    }
    return maxIndex;
  }

  private static List<Integer> serializeTree(TreeNode root) {
    List<Integer> serialized = new ArrayList<>();
    if (root == null) {
      return serialized;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      TreeNode current = queue.poll();
      if (current != null) {
        serialized.add(current.val);
        queue.offer(current.left);
        queue.offer(current.right);
      } else {
        serialized.add(null);
      }
    }

    // Remove trailing nulls for a cleaner representation
    int i = serialized.size() - 1;
    while (i >= 0 && serialized.get(i) == null) {
      serialized.remove(i);
      i--;
    }

    return serialized;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 4, 3, 1, 7, 0, 5 };
    TreeNode tree1 = solution.buildMaximumBinaryTree(nums1);
    List<Integer> output1 = serializeTree(tree1);
    System.out.println("Example 1 Output: " + output1);
    // Expected Output: [7, 4, 5, null, 3, 0, null, null, 1]

    // Example 2
    int[] nums2 = { 1, 4, 3, 2 };
    TreeNode tree2 = solution.buildMaximumBinaryTree(nums2);
    List<Integer> output2 = serializeTree(tree2);
    System.out.println("Example 2 Output: " + output2);
    // Expected Output: [4, 1, 3, null, null, null, 2]

    // Example 3
    int[] nums3 = { 7, 2, 5, 3, 9, 1 };
    TreeNode tree3 = solution.buildMaximumBinaryTree(nums3);
    List<Integer> output3 = serializeTree(tree3);
    System.out.println("Example 3 Output: " + output3);
    // Expected Output: [9, 7, 1, null, 5, null, null, 2, 3]
  }
}

Complexity Analysis

Time Complexity:

• Finding the Maximum Index:

  • The findIndexOfMaximum method scans the subarray from start to end - 1 to locate the maximum value. In the worst-case scenario (e.g., when the array is sorted in decreasing order), this scan takes time for each recursive call.

• Recursive Tree Construction:

  • The buildTree method is called recursively for the left and right subarrays. In the worst case, where each recursive call only reduces the problem size by one (e.g., sorted in decreasing order), the depth of recursion becomes n.
  • At each level of recursion, finding the maximum takes time, leading to a total time complexity of .

• Overall Time Complexity:

  • The dominant factor is the recursive tree construction with time complexity. Thus, the overall time complexity of the algorithm is .

Space Complexity:

• Recursive Call Stack:
  • The depth of the recursion tree depends on the structure of the input array. In the worst case (e.g., sorted in decreasing order), the recursion depth becomes n, leading to space consumed by the call stack.
• Tree Storage:

  • The constructed binary tree consists of n nodes, each occupying constant space. Therefore, storing the tree requires space.

• Overall Space Complexity:
  • The dominant factors are the recursion stack and the storage for the tree and serialization, each requiring space. Thus, the overall space complexity of the algorithm is .