Problem Description

You're given a maximum binary tree and need to insert a new value into it. A maximum tree is a special binary tree where every node's value is greater than all values in its subtree.

The tree was originally built from an array using this construction process:

• Find the largest element in the array and make it the root
• Elements to the left of the maximum form the left subtree (built recursively)
• Elements to the right of the maximum form the right subtree (built recursively)

Now you need to insert a new value val at the end of the original array and rebuild the tree following the same rules.

Key insight: Since val is appended to the end of the array, it affects how the tree is reconstructed:

• If val is larger than the current root, it becomes the new root with the entire original tree as its left child
• If val is smaller than the current root, it must be inserted somewhere in the right subtree (since it comes after all existing elements in the array)

The solution uses recursion to handle these two cases:

1. If root is None or root.val < val: Create a new node with val as the root and the current tree as its left child
2. Otherwise: Recursively insert val into the right subtree

This maintains the maximum tree property while respecting the position of val at the end of the original array.

Intuition

Let's think about what happens when we append a value to the original array and reconstruct the tree.

Since val is added at the end of the array, it's the rightmost element. When we apply the construction algorithm, we need to consider where this new element fits in the tree structure.

Consider two scenarios:

Scenario 1: val is the largest element in the entire array (including the new value).

• The construction algorithm would pick val as the root
• Everything to its left (the entire original array) becomes the left subtree
• There's nothing to its right, so no right subtree

Scenario 2: val is not the largest element.

• The root remains the same (still the maximum from the original array)
• Since val comes after the root element in the array, it must be part of the right subtree
• We recursively apply the same logic to the right subtree

The key realization is that we're essentially finding the correct position for val by traversing down the right spine of the tree. We keep going right until we find a node whose value is less than val. At that point, val becomes the new parent of that node.

Why only traverse right? Because val is appended at the end of the array, it can never be in anyone's left subtree - left subtrees are built from elements that come before the root in the array, but val comes after everything else.

This leads to the elegant recursive solution: either val becomes the new root (if it's larger than the current root), or we recursively insert it into the right subtree.

Learn more about Tree and Binary Tree patterns.

Solution Approach

The solution implements a recursive approach that handles two key cases based on comparing val with the current node's value.

Base Case & Case 1: When val is larger than the current root

if root is None or root.val < val:
    return TreeNode(val, root)

• If we've reached a None node (empty subtree) or the current root's value is less than val
• Create a new node with val as its value
• Make the entire current subtree the left child of this new node
• Return this new node as the new root of this subtree

Case 2: When val is smaller than the current root

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

• The current root remains unchanged
• Recursively insert val into the right subtree
• Update the root's right child with the result of the recursive call
• Return the root (structure preserved except for the modified right subtree)

Why this works:

1. The algorithm maintains the maximum tree property: when val becomes a new root, it's guaranteed to be larger than everything in its left subtree (the old tree)
2. By only traversing and modifying the right path, we respect the original array ordering where val was appended at the end
3. The recursion naturally finds the correct insertion point - the first node smaller than val along the right spine

Time Complexity: O(h) where h is the height of the tree. In the worst case (skewed tree), this could be O(n).

Space Complexity: O(h) for the recursion stack, which could be O(n) in the worst case.

Example Walkthrough

Let's walk through inserting val = 4 into this maximum tree:

Initial tree:        Array representation: [4, 1, 3, null, null, 2]
      5              Original array that built this: [1, 5, 3, 2]
     / \             We want to insert: val = 4
    1   3
       /
      2

Step 1: Start at root (5)

• Compare: 5 < 4? No, 5 is not less than 4
• Since 4 is smaller than 5, we need to insert 4 into the right subtree
• Call insertIntoMaxTree(root.right, 4) where root.right is node 3

Step 2: Now at node 3

• Compare: 3 < 4? Yes!
• Since 3 is less than 4, we create a new node with value 4
• The entire subtree rooted at 3 becomes the left child of this new node 4
• Return this new node 4

Step 3: Back to root (5)

• Update root.right with the returned node 4
• The final tree structure:

Final tree:          New array representation: [1, 5, 3, 2, 4]
      5              
     / \             
    1   4    ← 4 becomes the new right child of 5
       /
      3      ← The entire subtree (3 and its children) 
     /          becomes the left child of 4
    2

Let's verify this makes sense with the original array construction:

• Original array: [1, 5, 3, 2] → After insertion: [1, 5, 3, 2, 4]
• 5 is still the maximum, so it remains the root
• Elements left of 5: [1] forms the left subtree
• Elements right of 5: [3, 2, 4] forms the right subtree
  • In [3, 2, 4], the maximum is 4, so 4 becomes the root of this subtree
  • Elements left of 4: [3, 2] forms 4's left subtree (with 3 as root, 2 as its left child)
  • Elements right of 4: none, so no right subtree

The algorithm correctly found that 4 should be inserted as the parent of node 3, maintaining both the maximum tree property and the array ordering constraint.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the tree.

In the worst case, when the value val needs to be inserted at the rightmost position of the tree (i.e., when val is smaller than all existing node values), the algorithm traverses from the root down the right spine of the tree. Since the tree is constructed from a maximum array where each node is the maximum of its subtree, the worst case involves visiting all nodes along the rightmost path. In a skewed tree, this could be all n nodes, resulting in O(n) time complexity.

Space Complexity: O(n) where n is the number of nodes in the tree.

The space complexity is determined by the recursive call stack. In the worst case, when the tree is completely skewed to the right (forming a linked list-like structure), the recursion depth equals the number of nodes n. Each recursive call uses O(1) space for its local variables, but the call stack can grow up to O(n) levels deep, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Inserting into the Left Subtree

The Mistake: A common error is thinking that when val is smaller than the root, we should check both left and right subtrees to find the appropriate insertion point, similar to a binary search tree insertion.

# INCORRECT approach
def insertIntoMaxTree(self, root, val):
    if root is None or root.val < val:
        return TreeNode(val, root)
  
    # Wrong: Checking left subtree
    if root.left and root.left.val < val:
        root.left = self.insertIntoMaxTree(root.left, val)
    else:
        root.right = self.insertIntoMaxTree(root.right, val)
  
    return root

Why This is Wrong: The key constraint is that val is appended to the END of the original array. All elements in the left subtree came BEFORE the root in the original array, while val comes AFTER everything. Therefore, val can never be inserted into the left subtree.

Correct Solution: Always insert into the right subtree when val is smaller than the current root:

def insertIntoMaxTree(self, root, val):
    if root is None or root.val < val:
        return TreeNode(val, root)
  
    # Always go right when val is smaller
    root.right = self.insertIntoMaxTree(root.right, val)
    return root

Pitfall 2: Forgetting to Update the Parent's Reference

The Mistake: Simply calling the recursive function without updating the parent node's reference:

# INCORRECT: Not updating the reference
def insertIntoMaxTree(self, root, val):
    if root is None or root.val < val:
        return TreeNode(val, root)
  
    # Wrong: Not updating root.right with the result
    self.insertIntoMaxTree(root.right, val)  # Result is lost!
    return root

Why This is Wrong: When the recursive call creates a new subtree structure (especially when val becomes a new root of a subtree), we need to update the parent's reference to point to this new structure. Without the assignment, the tree modification is lost.

Correct Solution: Always assign the result of the recursive call back to the parent's child reference:

def insertIntoMaxTree(self, root, val):
    if root is None or root.val < val:
        return TreeNode(val, root)
  
    # Correct: Update root.right with the new subtree
    root.right = self.insertIntoMaxTree(root.right, val)
    return root

Pitfall 3: Misunderstanding the Tree Construction When val > root

The Mistake: When creating a new root because val is larger, incorrectly placing the old tree as the RIGHT child:

# INCORRECT placement
def insertIntoMaxTree(self, root, val):
    if root is None or root.val < val:
        # Wrong: Making old tree the right child
        return TreeNode(val, None, root)
  
    root.right = self.insertIntoMaxTree(root.right, val)
    return root

Why This is Wrong: In the original array, all existing elements come BEFORE the new val. When val becomes the new maximum (root), all previous elements should be in its LEFT subtree, not right.

Correct Solution: The old tree becomes the LEFT child of the new root:

def insertIntoMaxTree(self, root, val):
    if root is None or root.val < val:
        # Correct: Old tree becomes left child
        return TreeNode(val, root, None)  # or TreeNode(val, root)
  
    root.right = self.insertIntoMaxTree(root.right, val)
    return root