Difficulty: 🟡 Medium
Topics: Tree, Binary Tree

Solution

LeetCode 998 - Maximum Binary Tree II

Problem Statement

A maximum tree is a special binary tree where every node contains a value greater than all values inside its subtree. The tree is built recursively from an array by choosing the maximum element as the root, then recursively constructing the left subtree from the elements before the maximum value and the right subtree from the elements after the maximum value.

In this problem, we are not directly given the original array. Instead, we are given the root of an already constructed maximum binary tree and a new integer val. The problem guarantees that this new value was appended to the end of the original array.

Our task is to construct the new maximum tree that would result after appending val to the original array.

The important observation is that appending a value to the array only affects the right side of the tree. Since the new element is added at the end, it can never appear in the left subtree of any existing node. This structural property is what allows an efficient solution.

The constraints are relatively small, with at most 100 nodes, but the goal is still to understand the optimal structural approach rather than rebuilding the entire tree unnecessarily.

Several edge cases are important:

The new value may be larger than the current root, meaning it becomes the new root of the entire tree.
The new value may be smaller than all existing nodes, meaning it gets inserted somewhere along the right spine.
The tree may consist of only one node.
The insertion point may occur deep in the right subtree.

The problem also guarantees that all values are unique, which avoids ambiguity when determining maximum relationships.

Approaches

Brute Force Approach

A straightforward approach is to reconstruct the original array from the given tree, append val, and then rebuild the maximum binary tree from scratch.

To reconstruct the array, we can perform an inorder traversal of the maximum tree. This works because the original construction preserves the inorder sequence of the array elements.

After obtaining the array:

Perform inorder traversal to recover the original array.
Append val.
Rebuild the maximum tree recursively using the standard construction algorithm.

This approach is correct because it exactly simulates the original problem definition. However, rebuilding the tree repeatedly searches for maximum elements in subarrays, which can become inefficient.

Optimal Approach

The key insight comes from understanding how appending affects a maximum tree.

Since val is appended to the end of the array, it can only appear somewhere along the rightmost path of the existing tree.

There are only two possibilities:

If val is greater than the current root, then val becomes the new root, and the entire existing tree becomes its left child.
Otherwise, we continue searching in the right subtree because appended elements only affect the right side.

This observation allows us to recursively traverse only the right spine of the tree until we find the correct insertion point.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Rebuilds the entire tree from reconstructed array
Optimal	O(h)	O(h)	Traverses only the right spine of the tree

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

Start at the root of the maximum tree.
Compare val with the current node's value.
If val is greater than the current node value, create a new node containing val. Make the current tree the left child of this new node, then return the new node as the new root.
Otherwise, the insertion must happen somewhere in the right subtree because the new value was appended to the array and therefore belongs to the right side.
Recursively insert into the right subtree.
After recursion returns, reconnect the updated right subtree back to the current node.
Return the current node.

The recursion naturally walks down the right spine until it finds the correct insertion point.

Why it works

The algorithm works because appending an element to the array only changes the right boundary of the maximum tree.

If the appended value is larger than a node, it must become the parent of that node and everything to its left. If it is smaller, it must remain somewhere inside the right subtree because appended elements appear after all previous elements in the inorder ordering.

By recursively traversing the right side, we preserve the exact structural properties of the maximum tree construction process.

Python Solution

# 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 not root:
            return TreeNode(val)

        if val > root.val:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root

        root.right = self.insertIntoMaxTree(root.right, val)
        return root

The implementation directly follows the recursive logic described earlier.

The first base case handles an empty subtree. When we reach a None node, we create a new node containing val.

The second condition checks whether val is larger than the current root. If so, the new value must become the parent node because maximum tree roots always contain the largest value in the subtree.

If neither condition applies, we recursively continue into the right subtree. This preserves the inorder structure corresponding to appending an element at the end of the original array.

Finally, we reconnect the updated right subtree and return the current node.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }

    if val > root.Val {
        return &TreeNode{
            Val:  val,
            Left: root,
        }
    }

    root.Right = insertIntoMaxTree(root.Right, val)
    return root
}

The Go implementation mirrors the Python solution closely.

The primary difference is explicit pointer handling. In Go, tree nodes are manipulated through pointers, so newly created nodes use &TreeNode{} syntax.

Go also uses nil instead of Python's None.

Since the constraints are small and values are within integer range limits, integer overflow is not a concern.

Worked Examples

Example 1

Input:

root = [4,1,3,null,null,2]
val = 5

Current tree:

We compare 5 with root value 4.

Step	Current Node	val > node.val	Action
1	4	Yes	Create new root 5

New tree:

Output:

[5,4,null,1,3,null,null,2]

Example 2

Input:

root = [5,2,4,null,1]
val = 3

Current tree:

Traversal process:

Step	Current Node	val > node.val	Action
1	5	No	Move right
2	4	No	Move right
3	nil	N/A	Insert node 3

Updated tree:

Output:

[5,2,4,null,1,null,3]

Example 3

Input:

root = [5,2,3,null,1]
val = 4

Current tree:

Traversal process:

Step	Current Node	val > node.val	Action
1	5	No	Move right
2	3	Yes	Create new node 4

Node 4 becomes parent of subtree rooted at 3.

Updated tree:

Output:

[5,2,4,null,1,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h)	Traverses only the height of the tree
Space	O(h)	Recursive call stack depth

The algorithm only follows the right spine of the tree. In the worst case, the tree may become completely skewed, giving height h = n. In balanced scenarios, the height is much smaller.

No additional data structures are required besides recursion stack space.

Test Cases

# Helper utilities for testing

from collections import deque

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, val):
        if not root:
            return TreeNode(val)

        if val > root.val:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root

        root.right = self.insertIntoMaxTree(root.right, val)
        return root

def build_tree(values):
    if not values:
        return None

    nodes = [None if v is None else TreeNode(v) for v in values]
    kids = deque(nodes[1:])
    root = nodes[0]

    for node in nodes:
        if node:
            if kids:
                node.left = kids.popleft()
            if kids:
                node.right = kids.popleft()

    return root

def tree_to_list(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

solution = Solution()

# Example 1
root = build_tree([4,1,3,None,None,2])
result = solution.insertIntoMaxTree(root, 5)
assert tree_to_list(result) == [5,4,None,1,3,None,None,2]  # new value becomes root

# Example 2
root = build_tree([5,2,4,None,1])
result = solution.insertIntoMaxTree(root, 3)
assert tree_to_list(result) == [5,2,4,None,1,None,3]  # insert at rightmost position

# Example 3
root = build_tree([5,2,3,None,1])
result = solution.insertIntoMaxTree(root, 4)
assert tree_to_list(result) == [5,2,4,None,1,3]  # insert between nodes

# Single node, larger value
root = build_tree([1])
result = solution.insertIntoMaxTree(root, 2)
assert tree_to_list(result) == [2,1]  # new root created

# Single node, smaller value
root = build_tree([5])
result = solution.insertIntoMaxTree(root, 3)
assert tree_to_list(result) == [5,None,3]  # inserted as right child

# Deep right insertion
root = build_tree([10,None,8,None,7])
result = solution.insertIntoMaxTree(root, 6)
assert tree_to_list(result) == [10,None,8,None,7,None,6]  # append deep in chain

# Insert in middle of right spine
root = build_tree([10,None,7,None,5])
result = solution.insertIntoMaxTree(root, 6)
assert tree_to_list(result) == [10,None,7,None,6,5]  # inserted above smaller node

Test	Why
Example 1	Validates creation of a new root
Example 2	Validates insertion at deepest right position
Example 3	Validates insertion between existing nodes
Single node, larger value	Tests smallest tree with root replacement
Single node, smaller value	Tests right child insertion
Deep right insertion	Tests recursive traversal depth
Insert in middle of right spine	Tests subtree restructuring

Edge Cases

One important edge case occurs when the new value is larger than the current root. This can easily cause bugs if the implementation forgets to preserve the existing tree as the left child of the new node. The correct behavior is to create a new root and attach the entire previous tree underneath it.

Another important case occurs when the new value is smaller than every node in the tree. In this situation, the algorithm must traverse all the way down the right spine until it reaches a null position. Incorrect implementations may accidentally insert too early and violate the maximum tree property.

A third edge case involves insertion in the middle of the right spine. This happens when the new value is greater than some right descendant but smaller than its ancestors. The implementation must correctly place the new node between those nodes while preserving the subtree structure. The recursive approach handles this naturally because the smaller subtree becomes the left child of the inserted node.

Finally, very small trees such as a single-node tree are important to handle correctly. These cases verify that the base cases are properly implemented and that null children are processed safely without dereferencing errors.