Problem Description

The Maximum Binary Tree II problem is a variation of the original Maximum Binary Tree construction. You are given the root of a maximum binary tree (let's call it root) constructed from an array a (with distinct elements), and a value val that was not present in a. You are to insert val into the array a (at the end) and then return the root of the new maximum binary tree constructed from this new array.

• The maximum binary tree is built as follows:
  • The root is the maximum element in the array.
  • The left subtree is the maximum binary tree constructed from the subarray left of the maximum value.
  • The right subtree is the maximum binary tree constructed from the subarray right of the maximum value.
• val is guaranteed to be unique and not present in a.
• You should not reconstruct the tree from scratch; instead, modify the given tree directly to reflect the insertion.

Thought Process

At first glance, the brute-force approach is to reconstruct the new array by appending val to the end, then rebuild the maximum binary tree from scratch. However, this is inefficient because the original tree structure is already available and only needs to be updated to reflect the insertion of a new element at the end.

The key insight is to mimic what would have happened if val had been present at the end of the original array during the tree's construction. Since val is only appended at the end, it can only affect the rightmost path of the tree (the path you get by always going right from the root). If val is greater than any node along this path, it becomes the new root or the right child of a node on this path. Otherwise, it will be attached as the rightmost leaf.

We can optimize by traversing only the rightmost path, stopping when we find where val should be attached.

Solution Approach

Let's break down the algorithm step by step:

1. Create a new node for val (let's call it newNode).
2. Check if val is greater than the root's value:
   • If so, newNode becomes the new root, and the old root becomes its left child.
3. Otherwise:
   • Traverse the rightmost path of the tree, looking for the first node whose right child is null or whose right child's value is less than val.
   • Insert newNode as the right child of this node, and set newNode.left to the previous right child (if any).
4. Return the updated root.

This approach is efficient because it only traverses the rightmost path, which is at most O(h), where h is the height of the tree.

Example Walkthrough

Let's walk through an example:

Suppose the original array is [5,2,4,1], so the tree looks like:

• Root: 5
• 5's right: 4
• 4's left: 2
• 4's right: 1
• 2 and 1 have no children

Now, val = 3. We append 3 to the array: [5,2,4,1,3].

1. Step 1: Create a new node for 3.
2. Step 2: Traverse right from 5 to 4, then right from 4 to 1 (since 3 > 1), stop here.
3. Step 3: Insert 3 as the right child of 1. 1's right was null, so 3's left is null.
4. Step 4: The updated tree now represents the maximum binary tree for [5,2,4,1,3].

If instead val = 6, since 6 > 5 (root), 6 becomes the new root, and the entire previous tree becomes its left child.

Code Implementation

# 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: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        if val > root.val:
            return TreeNode(val, left=root)
        curr = root
        while curr.right and curr.right.val > val:
            curr = curr.right
        newNode = TreeNode(val)
        newNode.left = curr.right
        curr.right = newNode
        return root
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        if (val > root->val) {
            TreeNode* node = new TreeNode(val);
            node->left = root;
            return node;
        }
        TreeNode* curr = root;
        while (curr->right && curr->right->val > val) {
            curr = curr->right;
        }
        TreeNode* node = new TreeNode(val);
        node->left = curr->right;
        curr->right = node;
        return root;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val > root.val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        TreeNode curr = root;
        while (curr.right != null && curr.right.val > val) {
            curr = curr.right;
        }
        TreeNode node = new TreeNode(val);
        node.left = curr.right;
        curr.right = node;
        return root;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoMaxTree = function(root, val) {
    if (!root) return new TreeNode(val);
    if (val > root.val) {
        return new TreeNode(val, root, null);
    }
    let curr = root;
    while (curr.right && curr.right.val > val) {
        curr = curr.right;
    }
    let node = new TreeNode(val);
    node.left = curr.right;
    curr.right = node;
    return root;
};
      

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n), since rebuilding the tree from the new array takes O(n) time.
  • Space Complexity: O(n), for the recursion stack (if building recursively) and the new tree.
• Optimized approach (as above):
  • Time Complexity: O(h), where h is the height of the tree (worst case O(n) if the tree is skewed, but much less for balanced trees).
  • Space Complexity: O(1) extra (if done iteratively), not counting the new node.

The optimized solution is preferred as it minimizes unnecessary reconstruction and leverages the properties of the maximum binary tree.

Summary

The Maximum Binary Tree II problem challenges us to efficiently update a maximum binary tree after appending a unique value to the original array. By recognizing that the new value only affects the rightmost path, we avoid full reconstruction and instead insert the new node in the correct spot with a simple traversal. This approach is both elegant and efficient, making the most of the tree's structure and constraints.