Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructMaximumBinaryTree(self, nums):
        if not nums:
            return None
        max_val = max(nums)
        max_idx = nums.index(max_val)
        root = TreeNode(max_val)
        root.left = self.constructMaximumBinaryTree(nums[:max_idx])
        root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])
        return root
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size());
    }
    TreeNode* build(const vector<int>& nums, int l, int r) {
        if (l == r) return nullptr;
        int max_idx = l;
        for (int i = l; i < r; ++i) {
            if (nums[i] > nums[max_idx]) max_idx = i;
        }
        TreeNode* root = new TreeNode(nums[max_idx]);
        root->left = build(nums, l, max_idx);
        root->right = build(nums, max_idx + 1, r);
        return root;
    }
};
      

// 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 build(nums, 0, nums.length);
    }
    private TreeNode build(int[] nums, int l, int r) {
        if (l == r) return null;
        int maxIdx = l;
        for (int i = l; i < r; i++) {
            if (nums[i] > nums[maxIdx]) maxIdx = i;
        }
        TreeNode root = new TreeNode(nums[maxIdx]);
        root.left = build(nums, l, maxIdx);
        root.right = build(nums, maxIdx + 1, r);
        return root;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    if (nums.length === 0) return null;
    let maxVal = Math.max(...nums);
    let maxIdx = nums.indexOf(maxVal);
    let root = new TreeNode(maxVal);
    root.left = constructMaximumBinaryTree(nums.slice(0, maxIdx));
    root.right = constructMaximumBinaryTree(nums.slice(maxIdx + 1));
    return root;
};
      

Problem Description

Given an array nums of distinct integers, construct a maximum binary tree as follows:

• The root is the maximum number in nums.
• The left subtree is the maximum binary tree constructed from the elements left of the maximum number.
• The right subtree is the maximum binary tree constructed from the elements right of the maximum number.

Return the root node of the constructed binary tree.

Constraints:

• All elements in nums are unique.
• Each element is used exactly once (do not reuse elements).
• There is only one valid solution for each input.

Thought Process

The problem asks us to build a binary tree by repeatedly finding the maximum element in a (sub)array, making it the root, and recursively building left and right subtrees from the elements to its left and right.

At first glance, a brute-force approach comes to mind: for each subarray, find the maximum element (which takes time), then recursively build left and right subtrees. This is straightforward but may not be efficient for large arrays.

To optimize, we notice that each recursive call works on a smaller part of the array, and the process is similar to how quicksort partitions an array. There are also advanced stack-based solutions for linear time, but the recursive approach is easier to understand and sufficient for most constraints.

The key insight is that the problem is naturally recursive: each subtree is itself a maximum binary tree of a subarray.

Solution Approach

We solve the problem recursively. Here is the step-by-step approach:

1. Base Case: If the input array (or subarray) is empty, return null (or None).
2. Find the Maximum: Search for the maximum value in the current array segment. This value becomes the root of the current subtree.
3. Divide the Array: Split the array into two parts:
   • Left part: all elements to the left of the maximum (not including the maximum itself).
   • Right part: all elements to the right of the maximum.
4. Recursive Construction: Recursively build the left subtree from the left part and the right subtree from the right part.
5. Attach Subtrees: Set the left and right children of the root node to the results of the recursive calls.
6. Return Root: Return the root node for this segment.

This approach is intuitive and directly follows the problem's definition. For large arrays, you can optimize the maximum search using a monotonic stack, but the recursive solution is easy to implement and understand.

Example Walkthrough

Let's walk through an example with nums = [3, 2, 1, 6, 0, 5]:

1. Find the maximum: 6 at index 3. This becomes the root.
   • Left part: [3, 2, 1]
   • Right part: [0, 5]
2. Build left subtree from [3, 2, 1]:
   • Maximum: 3 at index 0. Root of this subtree.
   • Left: [] (empty, so left child is null)
   • Right: [2, 1]
   • Build right subtree from [2, 1]:
     • Maximum: 2 at index 0. Root of this subtree.
     • Left: []
     • Right: [1]
     • Build right subtree from [1]:
       • Maximum: 1. Both left and right are empty arrays.
3. Build right subtree from [0, 5]:
   • Maximum: 5 at index 1. Root of this subtree.
   • Left: [0]
   • Right: []
   • Build left subtree from [0]:
     • Maximum: 0. Both left and right are empty arrays.

The final tree structure:

• 6 is the root
• 6's left: 3, whose right is 2, whose right is 1
• 6's right: 5, whose left is 0

Time and Space Complexity

Brute-force Recursive Approach:

• Each recursive call scans the current subarray to find the maximum (O(n) time for n elements).
• There are n nodes in the tree, so in the worst case (unbalanced, e.g., sorted array), time complexity is O(n²).
• Space complexity is O(n) for the recursion stack and tree nodes.

• Time complexity: O(n) by using a monotonic stack to find parent-child relationships in one pass.
• Space complexity: O(n).

Summary

The Maximum Binary Tree problem is a classic example of recursive divide-and-conquer. By always choosing the maximum element as the root and splitting the array, we build the tree according to the problem's requirements. The recursive approach is intuitive and easy to implement, though it can be optimized further for large inputs. The elegance of the solution lies in how closely the code mirrors the problem's definition, making it both readable and reliable.