# Maximum Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/maximum-binary-tree
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Stack, Monotonic Stack, Tree, Binary Tree
---
## Problem
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`.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-binary-tree/image0.jpg) 

**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.

**Example 2:**

![](https://assets.glich.co/dsa/maximum-binary-tree/image1.jpg) 

**Input:** nums = [3,2,1]
**Output:** [3,null,2,null,1]

**Constraints:**

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

# Approaches
## Recursive Construction
This approach is a direct translation of the problem's definition into a recursive algorithm. It works by finding the maximum element in the current range of the array, making it the root of a subtree, and then recursively performing the same process for the left and right subarrays formed by splitting the array at the maximum element's position.
**Time:** O(n^2) in the worst case. For each node created, we might scan a large portion of the array to find the next maximum. In the worst case (a sorted array), the work done is proportional to `n + (n-1) + ... + 1`, which is O(n^2). The average case is O(n log n). · **Space:** O(n) in the worst case. The recursion depth can be up to `n` for a skewed tree (e.g., a sorted array), which consumes O(n) space on the call stack.
**Pros:** Simple to understand and implement as it directly follows the problem description.; It's a good starting point for solving the problem.
**Cons:** The repeated scanning for the maximum element in overlapping subarrays is inefficient.; Leads to a quadratic time complexity in the worst-case scenario (e.g., a sorted input array).
### Explanation
The core of this method is a helper function that takes the array and two indices, `left` and `right`, defining the current subarray to be processed. In each call, the function scans this subarray to find the maximum value and its index. This maximum value becomes the value of the new root `TreeNode`. The function then calls itself recursively to build the left subtree from the part of the array to the left of the maximum element (`left` to `maxIndex - 1`) and the right subtree from the part to the right (`maxIndex + 1` to `right`). The base case for the recursion is when the `left` index becomes greater than the `right` index, indicating an empty subarray, for which `null` is returned.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // Find the index of the maximum element in the current range
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

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

        // Recursively build the left and right subtrees
        root.left = build(nums, left, maxIndex - 1);
        root.right = build(nums, maxIndex + 1, right);

        return root;
    }
}
```
### Algorithm
*   Define a recursive function `build(nums, left, right)` that constructs a tree from the subarray `nums[left...right]`.
*   **Base Case:** If `left > right`, the subarray is empty, so return `null`.
*   **Recursive Step:**
    1.  Find the index `maxIndex` of the maximum element within `nums[left...right]` by linearly scanning the subarray.
    2.  Create a new `TreeNode` with the value `nums[maxIndex]`. This is the root of the current subtree.
    3.  The left child of this root is the result of a recursive call on the subarray to the left of the maximum element: `build(nums, left, maxIndex - 1)`.
    4.  The right child of this root is the result of a recursive call on the subarray to the right of the maximum element: `build(nums, maxIndex + 1, right)`.
    5.  Return the created root node.
*   The initial call to the function is `build(nums, 0, nums.length - 1)`.

## Single Pass with Monotonic Stack
This is a highly efficient O(n) approach that constructs the tree in a single pass. It utilizes a monotonic stack (specifically, a stack that keeps node values in decreasing order) to maintain the right spine of the tree built so far. As each new element from the input array is processed, the stack is adjusted to correctly position the new node in the tree by wiring up the parent-child relationships.
**Time:** O(n). Each node corresponding to a number in `nums` is pushed onto the stack exactly once and popped from the stack at most once. All operations are amortized constant time, leading to a linear time overall. · **Space:** O(n). The auxiliary space is for the stack. In the worst-case scenario (e.g., a descending sorted array like `[5, 4, 3, 2, 1]`), the stack will hold all `n` nodes.
**Pros:** Optimal time complexity of O(n).; Builds the tree in a single pass over the input array.; Efficient use of space.
**Cons:** The logic is more complex and less intuitive compared to the direct recursive approach.; Requires a solid understanding of monotonic stacks and their application.
### Explanation
The algorithm processes numbers from left to right. A stack is used to keep track of the nodes that form the 'right contour' or 'right spine' of the tree constructed so far. The values of nodes in the stack are always in decreasing order from bottom to top.

When we encounter a new number `num`, we create a `currentNode` for it. We then pop all nodes from the stack that have a value smaller than `num`. The last node popped (which is the largest among all popped nodes) becomes the left child of `currentNode`. This is because `currentNode` is the first element to their right that is larger than them. After this, if the stack is not empty, the node at the top of the stack has a value larger than `num`. This means `currentNode` must be the right child of that node. Finally, `currentNode` is pushed onto the stack to maintain the invariant.

After iterating through all the numbers, the node at the bottom of the stack is the root of the complete tree.

```java
import java.util.Deque;
import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new LinkedList<>();
        for (int num : nums) {
            TreeNode currentNode = new TreeNode(num);
            // Pop nodes from stack that are smaller than the current node.
            // The last popped node will become the left child of the current node.
            while (!stack.isEmpty() && stack.peekLast().val < num) {
                currentNode.left = stack.removeLast();
            }
            // If stack is not empty, the current node is the right child
            // of the node at the top of the stack.
            if (!stack.isEmpty()) {
                stack.peekLast().right = currentNode;
            }
            // Push the current node onto the stack.
            stack.addLast(currentNode);
        }
        // The root of the tree is the first element that was added to the stack.
        return stack.isEmpty() ? null : stack.getFirst();
    }
}
```
### Algorithm
*   Initialize an empty stack (a `Deque` is suitable) to store `TreeNode`s.
*   Iterate through each number `num` in the input array `nums`.
*   For each `num`, create a `currentNode = new TreeNode(num)`.
*   While the stack is not empty and the value of the node at the top of the stack is less than `num`:
    *   The node at the top of the stack is smaller than `currentNode`. This means `currentNode` is the first larger element to its right. Therefore, the top node must be in the left subtree of `currentNode`.
    *   Pop the node from the stack and set it as the left child of `currentNode`. `currentNode.left = stack.pop()`.
*   After the while loop, if the stack is not empty, the node now at the top is greater than `currentNode`. This means `currentNode` must be in its right subtree. Set `stack.peek().right = currentNode`.
*   Push `currentNode` onto the stack.
*   After iterating through all numbers, the root of the entire tree is the only element remaining at the bottom of the stack. Return `stack.getFirst()`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int [] nums ; public TreeNode constructMaximumBinaryTree ( int [] nums ) { this . nums = nums ; return dfs ( 0 , nums . length - 1 ); } private TreeNode dfs ( int l , int r ) { if ( l > r ) { return null ; } int i = l ; for ( int j = l ; j <= r ; ++ j ) { if ( nums [ i ] < nums [ j ]) { i = j ; } } TreeNode root = new TreeNode ( nums [ i ]); root . left = dfs ( l , i - 1 ); root . right = dfs ( i + 1 , r ); return root ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * constructMaximumBinaryTree ( vector < int >& nums ) { return dfs ( nums , 0 , nums . size () - 1 ); } TreeNode * dfs ( vector < int >& nums , int l , int r ) { if ( l > r ) return nullptr ; int i = l ; for ( int j = l ; j <= r ; ++ j ) { if ( nums [ i ] < nums [ j ]) { i = j ; } } TreeNode * root = new TreeNode ( nums [ i ]); root -> left = dfs ( nums , l , i - 1 ); root -> right = dfs ( nums , i + 1 , r ); return root ; } };
```

### Python

```python
# 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 : List [ int ]) -> Optional [ TreeNode ]: def dfs ( nums ): if not nums : return None val = max ( nums ) i = nums . index ( val ) root = TreeNode ( val ) root . left = dfs ( nums [: i ]) root . right = dfs ( nums [ i + 1 :]) return root return dfs ( nums )
```