Maximum Binary Tree

Problem Description

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Naive Solution

A brute-force approach would involve, for each subarray, finding the maximum element and recursively building the tree. This involves repeatedly scanning subarrays to find the maximum.

Algorithm

1. Find the maximum element in the current subarray.
2. Create a node with this maximum element as the value.
3. Recursively call the function for the left subarray (elements to the left of the maximum element).
4. Recursively call the function for the right subarray (elements to the right of the maximum element).
5. Return the created node.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def constructMaximumBinaryTree_naive(nums):
    if not nums:
        return None

    max_val = max(nums)
    max_index = nums.index(max_val)

    root = TreeNode(max_val)
    root.left = constructMaximumBinaryTree_naive(nums[:max_index])
    root.right = constructMaximumBinaryTree_naive(nums[max_index+1:])

    return root

Time Complexity

O(n^2) in the worst case, where n is the number of elements in nums. Finding the maximum element and its index in each subarray takes O(n) time, and this operation is performed for each node in the tree.

Space Complexity

O(n) due to the recursive call stack. In the worst case (skewed tree), the depth of the recursion can be n.

Optimal Solution

A more efficient approach involves using a stack to keep track of potential parent nodes. This avoids repeatedly scanning subarrays to find the maximum element.

Algorithm

1. Initialize an empty stack.
2. Iterate through the nums array.
   • For each element, create a TreeNode.
   • While the stack is not empty and the current element is greater than the top of the stack, pop the top element and make it the left child of the current node.
   • If the stack is not empty, make the current node the right child of the top of the stack.
   • Push the current node onto the stack.
3. The last element remaining in the stack is the root of the tree.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def constructMaximumBinaryTree(nums):
    stack = []
    for num in nums:
        node = TreeNode(num)
        while stack and num > stack[-1].val:
            node.left = stack.pop()
        if stack:
            stack[-1].right = node
        stack.append(node)
    return stack[0]

Time Complexity

O(n), where n is the number of elements in nums. Each element is pushed onto and popped from the stack at most once.

Space Complexity

O(n) in the worst case, where n is the number of elements in nums. The stack can contain all the elements if the input array is sorted in ascending order.

Edge Cases

• Empty input array: The function should return None.
• Single-element array: The function should return a tree with a single node.
• Array with duplicate values: The problem statement specifies that the input array contains no duplicates.