> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/binary-tree/problems-related-to-binary-trees/22.-maximum-binary-tree.md).

# 22. 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`.

**Example 1:**![](https://assets.leetcode.com/uploads/2020/12/24/tree1.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.leetcode.com/uploads/2020/12/24/tree2.jpg)

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

## Solution: (Using Recursion)

```cpp
class Solution
{
public:
    int findMax(vector<int> nums, int start, int end)
    {

        int max = INT_MIN;
        int idx = -1;
        for (int i = start; i <= end; i++)
        {
            if (nums[i] > max)
            {
                max = nums[i];
                idx = i;
            }
        }
        return idx;
    }

    TreeNode *createTree(vector<int> nums, int start, int end)
    {
        if (start > end)
        {
            return NULL;
        }
        
        int idx = findMax(nums, start, end);
        TreeNode *t = new TreeNode;
        t->val = nums[idx];
        t->left = createTree(nums, start, idx - 1);
        t->right = createTree(nums, idx + 1, end);
        return t;
    }

    TreeNode *constructMaximumBinaryTree(vector<int> &nums)
    {
        TreeNode *t = createTree(nums, 0, nums.size() - 1);
        return t;
    }
};
```