Maximum Binary Tree

Problem Description

Given an integer array nums with no duplicates, construct a maximum binary tree as follows:

1. Create a root node with the maximum value in nums.
2. Recursively build the left subtree using the subarray to the left of the maximum value.
3. Recursively build the right subtree using the subarray to the right of the maximum value.

Return the constructed maximum binary tree.

Naive Approach

A straightforward approach is to recursively find the maximum element in the array, create a node for it, and then recursively call the function for the left and right subarrays. This approach involves repeatedly scanning subarrays to find the maximum element.

Code (Python)

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

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

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

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

    return root

Time Complexity

The time complexity is O(n^2) in the worst case, where n is the number of elements in nums. This is because, in each recursive call, we find the maximum element in O(n) time and make two recursive calls on subarrays.

Space Complexity

The space complexity is O(n) due to the recursion stack. In the worst case (e.g., sorted array), the recursion depth can be n.

Optimal Approach

A more efficient approach involves using a stack to keep track of potentially larger elements. This method reduces the time complexity by avoiding repeated scans for the maximum element. The algorithm processes the array from left to right, maintaining a stack of nodes that could be part of the left subtree of the current node.

Algorithm

1. Initialize an empty stack.
2. Iterate through the nums array.
3. For each element, create a new node.
4. While the stack is not empty and the top element of the stack has a value less than the current element, pop elements from the stack and make them the left child of the current node.
5. If the stack is not empty, make the current node the right child of the top element of the stack.
6. Push the current node onto the stack.
7. After processing all elements, the last element remaining in the stack is the root of the tree.

Code (Python)

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

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

Time Complexity

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

Space Complexity

The space complexity is O(n) because, in the worst-case scenario (e.g., a sorted array), all elements could be stored in the stack.

Edge Cases

• Empty input array: Return None.
• Single-element array: Return a tree with a single node.
• Array with duplicate elements (although the problem states there are no duplicates): The algorithm would still work, but the definition of a maximum binary tree would be ambiguous with duplicate values.

Summary

The optimal approach using a stack provides a more efficient way to construct the maximum binary tree with a time complexity of O(n) compared to the naive approach's O(n^2) time complexity. Both approaches have a space complexity of O(n).