# 0654. Maximum Binary Tree

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0654-maximum-binary-tree)

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`.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

```
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
We could solve this question in two ways:

1. **Recursive** Solution - **Find MAX** for left subtree and right subtree
2. **Iterative** Solution - Use **Monotonic Stack**
   {% endhint %}

> **Recursive Solution**

We need two functions (1) Helper for **constructing a binary tree** (2) **Find the MAX element** using the left and right boundaries.

The helper function recursively calls itself and the **termination condition is when left-boundary >= right-boundary**.

> **Iterative Solution**\
> Iterate through the input integer array and **use stack to record previous nodes**

1. **current node's value > previous node's value**\
   Keep popping from the stack and append the last node to the current node's left
2. **current node's value < previous node's value**\
   Append the current node to the previous node's right
3. **Push current node onto the stack**
   {% endtab %}
   {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3 (Monotic Stack)" %}

```python
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        # (base case)
        if not nums: return None
        if len(nums) == 1: return TreeNode(nums[0])
        
        # ==================================================
        #  Binary Tree + Monotonic Stack                   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        """
        input: [3,2,1,6,0,5]

        stack: [3]          3.left  = None
        stack: [3,2]        2.left  = None, 3.right = 2
        stack: [3,2,1]      1.left  = None, 2.right = 1
        stack: [6]          6.left  = 3
        stack: [6,0]        0.left  = None, 6.right = 0
        stack: [6,5]        5.left  = 0,    6.right = 5
        """
        
        stack = []
        for i in nums:
            node, last = TreeNode(i), None
            
            # (current node's value > previous node's value)
            #  1. pop from stack
            #  2. append the MAX element in the stack to current node's left
            while stack and stack[-1].val < i:
                last = stack.pop()
            node.left = last
            
            # (current node's value < previous node's value)
            # append current node to previous node's right
            if stack: stack[-1].right = node
            
            stack.append(node)
            
        return stack[0]
```

{% endtab %}

{% tab title="🤖 Python3 (Recursive)" %}

```python
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        # (base case)
        if not nums: return None
        if len(nums) == 1: return TreeNode(nums[0])
        
        # ==================================================
        #  Binary Tree + Recursion                         =
        # ==================================================
        # time  : O(n^2)
        # space : O(n)
        
        self.nums = nums
        return self.construct(0, len(nums))
        
    def construct(self, left: int, right: int) -> TreeNode:
        if left >= right: return None
        
        maxIndex = self.findMax(left, right)
        return TreeNode(self.nums[maxIndex], 
                        self.construct(left, maxIndex),
                        self.construct(maxIndex+1, right))
    
    def findMax(self, left: int, right: int) -> int:
        maxIndex = left
        for i in range(left, right):
            if self.nums[i] > self.nums[maxIndex]:
                maxIndex = i
                
        return maxIndex
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
public class Solution {
    /**
     * @time  : O(n^2)
     * @space : O(n)
     */
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        /* base case */
        if(nums.length == 0) return null;
        if(nums.length == 1) return new TreeNode(nums[0]);
        
        return construct(nums, 0, nums.length);
    }
    
    public TreeNode construct(int[] nums, int l, int r) {
        if (l >= r) return null;
        
        int max_i = max(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }
    
    public int max(int[] nums, int l, int r) {
        int max_i = l;
        for (int i = l; i < r; i++) {
            if (nums[max_i] < nums[i])
                max_i = i;
        }
        return max_i;
    }
}
```

{% endtab %}
{% endtabs %}