# Maximum Binary Tree II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-binary-tree-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-binary-tree-ii
**Data structures:** Tree, Binary Tree
---
## Problem
A **maximum tree** is a tree where every node has a value greater than any other value in its subtree.

You are given the `root` of a maximum binary tree and an integer `val`.

Just as in the [previous problem](https://leetcode.com/problems/maximum-binary-tree/), the given tree was constructed from a list `a` (`root = Construct(a)`) recursively with the following `Construct(a)` routine:

* If `a` is empty, return `null`.
* Otherwise, let `a[i]` be the largest element of `a`. Create a `root` node with the value `a[i]`.
* The left child of `root` will be `Construct([a[0], a[1], ..., a[i - 1]])`.
* The right child of `root` will be `Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]])`.
* Return `root`.

Note that we were not given `a` directly, only a root node `root = Construct(a)`.

Suppose `b` is a copy of `a` with the value `val` appended to it. It is guaranteed that `b` has unique values.

Return `Construct(b)`.

**Example 1:**

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

**Input:** root = [4,1,3,null,null,2], val = 5
**Output:** [5,4,null,1,3,null,null,2]
**Explanation:** a = [1,4,2,3], b = [1,4,2,3,5]

**Example 2:**

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

**Input:** root = [5,2,4,null,1], val = 3
**Output:** [5,2,4,null,1,null,3]
**Explanation:** a = [2,1,5,4], b = [2,1,5,4,3]

**Example 3:**

![](https://assets.glich.co/dsa/maximum-binary-tree-ii/image2.JPG) 

**Input:** root = [5,2,3,null,1], val = 4
**Output:** [5,2,4,null,1,3]
**Explanation:** a = [2,1,5,3], b = [2,1,5,3,4]

**Constraints:**

* The number of nodes in the tree is in the range `[1, 100]`.
* `1 <= Node.val <= 100`
* All the values of the tree are **unique**.
* `1 <= val <= 100`

# Approaches
## Reconstruct Array and Rebuild Tree
This approach follows a straightforward, brute-force method. First, it reconstructs the original array `a` from which the given maximum binary tree was built. Then, it appends the new value `val` to this array to form a new array `b`. Finally, it constructs a new maximum binary tree from the array `b` using the standard construction algorithm.
**Time:** O(N^2), where N is the number of nodes in the original tree. The in-order traversal takes O(N). The construction of the new tree from an array of size N+1 takes O((N+1)^2) because for each node, we scan a subarray to find the maximum. · **Space:** O(N). We need O(N) space to store the array `a` (and `b`). The recursion stack for both traversal and construction can go up to O(N) in the case of a skewed tree.
**Pros:** Conceptually simple and easy to understand.; Directly simulates the problem definition.
**Cons:** Highly inefficient. It rebuilds the entire tree from scratch, even though the change is localized.; Requires significant extra space to store the intermediate array.
### Explanation
The core idea is to reverse the construction process to get the original data, modify the data, and then re-apply the construction process.

**Step 1: Reconstruct the original array `a`**. A key property of the maximum binary tree is that an in-order traversal of the tree yields the original array `a`. We perform an in-order traversal on the given `root` and store the node values in a list.

**Step 2: Append `val` to form `b`**. After obtaining the list `a`, we simply append the new integer `val` to it to get the list `b`.

**Step 3: Construct the new tree from `b`**. We implement the `Construct(b)` routine as described in the problem. This function recursively finds the maximum element in the current segment of the array, creates a root with it, and then builds the left and right subtrees from the parts of the array to the left and right of the maximum element.

```java
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        List<Integer> a = new ArrayList<>();
        inorder(root, a);
        a.add(val);
        return construct(a, 0, a.size() - 1);
    }

    private void inorder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }

    private TreeNode construct(List<Integer> nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int maxIndex = -1;
        int maxVal = -1;
        for (int i = left; i <= right; i++) {
            if (nums.get(i) > maxVal) {
                maxVal = nums.get(i);
                maxIndex = i;
            }
        }
        TreeNode node = new TreeNode(maxVal);
        node.left = construct(nums, left, maxIndex - 1);
        node.right = construct(nums, maxIndex + 1, right);
        return node;
    }
}
```
### Algorithm
- Create an empty list, say `a`.
- Perform an in-order traversal on the input tree `root`. During the traversal, add each visited node's value to the list `a`.
- Append the given `val` to the list `a`.
- Construct a new maximum binary tree from the modified list `a` using the recursive construction algorithm.
- Return the root of the newly constructed tree.

## Recursive Insertion
This approach leverages the properties of the maximum binary tree construction. Since `val` is appended to the original array `a`, it will always be in the 'right part' of the array relative to any existing element. This means we only need to consider inserting `val` into the right spine of the tree. A recursive function can elegantly handle this insertion.
**Time:** O(H), where H is the height of the tree. In the worst case (a skewed tree), the height is O(N), making the time complexity O(N). We only traverse down the right spine. · **Space:** O(H) due to the recursion stack, where H is the height of the tree. In the worst case of a skewed tree, this is O(N).
**Pros:** Much more efficient than rebuilding the tree.; The logic directly follows the recursive definition of the tree construction.; The code is very concise and elegant.
**Cons:** Uses recursion, which can lead to a `StackOverflowError` for very deep trees (not an issue with the given constraints).; The space complexity is dependent on the tree's height.
### Explanation
The logic is based on where `val` fits in the construction of `b = a + [val]`. The main function itself can serve as the recursive function.

- **Base Case**: If `root` is `null`, it means we've reached a point where a new subtree needs to be created. The list that would form this subtree is empty, and we are adding `val`. `Construct([val])` is simply a new node with `val`. So, we return `new TreeNode(val)`.

- **Recursive Step 1**: If `val > root.val`. According to the construction rule, `val` is the new maximum for the list that formed the subtree at `root`. The new root will be a node with `val`. The entire original tree was formed from a list that is now entirely to the left of `val`. Therefore, the original `root` becomes the left child of the new node. The right child is `null`. We return `new TreeNode(val, root, null)`.

- **Recursive Step 2**: If `val < root.val`. The root of the current subtree (`root`) does not change. The new value `val` must belong to the right part of the list relative to `root.val`. Therefore, we need to insert `val` into the right subtree of `root`. We do this by making a recursive call: `root.right = insertIntoMaxTree(root.right, val)`. We then return the (unmodified) `root`.

```java
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        
        if (val > root.val) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}
```
### Algorithm
- Define a function `insertIntoMaxTree(root, val)`.
- **Base Case**: If `root` is `null`, return a new `TreeNode(val)`.
- If `val > root.val`, `val` becomes the new root. The original `root` becomes the left child of the new node. Create `newRoot = new TreeNode(val)`, set `newRoot.left = root`, and return `newRoot`.
- If `val < root.val`, `val` must be inserted into the right subtree. Recursively call `insertIntoMaxTree` on the right child: `root.right = insertIntoMaxTree(root.right, val)`.
- Return the `root`.

## Iterative Insertion on the Right Spine
This approach is an iterative optimization of the recursive solution. It avoids the recursion stack overhead by using a loop. The logic remains the same: since `val` is appended to the original array, we only need to find its correct position along the right spine of the tree.
**Time:** O(H), where H is the height of the tree. In the worst case (a skewed tree), this is O(N). The traversal is limited to the right spine of the tree. · **Space:** O(1). We only use a few pointers (`curr`, `newNode`), so the extra space is constant.
**Pros:** Optimal time complexity for this problem.; Optimal space complexity (O(1) extra space).; Avoids recursion, making it safe for very deep trees.
**Cons:** The iterative logic might be slightly less intuitive to come up with compared to the direct recursive translation.
### Explanation
This method achieves the same result as the recursive one but with constant extra space.

- **Case 1: `val` is the new maximum**. If `val > root.val`, `val` becomes the new root of the entire tree. The original tree becomes the left child of the new node. We create `new TreeNode(val, root, null)` and return it. This is the same as the recursive approach.

- **Case 2: `val` is not the new maximum**. If `val < root.val`, the root of the tree remains unchanged. We know `val` must be inserted somewhere in the right subtree. We need to find the first node on the right spine that is smaller than `val`.

- We start at the `root` and traverse down its right children. Let `curr` be the current node.

- We keep moving to the right child (`curr = curr.right`) as long as the right child exists and its value is greater than `val`.

- The loop `while (curr.right != null && curr.right.val > val)` finds the node `curr` which will be the parent of the new subtree containing `val`.

- Once the loop terminates, `curr` is the node whose right child will be replaced. The original `curr.right` subtree (which is either `null` or has a value less than `val`) will become the left child of the new node with `val`.

```java
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        TreeNode newNode = new TreeNode(val);
        
        if (root == null || val > root.val) {
            newNode.left = root;
            return newNode;
        }
        
        TreeNode curr = root;
        while (curr.right != null && curr.right.val > val) {
            curr = curr.right;
        }
        
        newNode.left = curr.right;
        curr.right = newNode;
        
        return root;
    }
}
```
### Algorithm
- Create a new node `newNode` with the value `val`.
- If `root` is `null` or `val > root.val`, set `newNode.left = root` and return `newNode`.
- Initialize a pointer `curr = root`.
- Traverse down the right spine of the tree: while `curr.right` is not `null` and `curr.right.val` is greater than `val`, update `curr = curr.right`.
- After the loop, `curr` is the parent node for the new subtree.
- Set `newNode.left` to `curr.right` (attaching the rest of the right spine).
- Set `curr.right` to `newNode`.
- Return the original `root`.

# 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 { public TreeNode insertIntoMaxTree ( TreeNode root , int val ) { if ( root == null || root . val < val ) { return new TreeNode ( val , root , null ); } root . right = insertIntoMaxTree ( root . right , val ); 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 * insertIntoMaxTree ( TreeNode * root , int val ) { if ( ! root || root -> val < val ) return new TreeNode ( val , root , nullptr ); root -> right = insertIntoMaxTree ( root -> right , val ); 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 insertIntoMaxTree ( self , root : Optional [ TreeNode ], val : int ) -> Optional [ TreeNode ]: if root is None or root . val < val : return TreeNode ( val , root ) root . right = self . insertIntoMaxTree ( root . right , val ) return root
```