Maximum Binary Tree II - Video Solutions

Problem Overview: You are given the root of a maximum binary tree built from an array and a new value val appended to that array. The task is to update the tree so it represents the maximum binary tree of the new array after the insertion.

A maximum binary tree has two rules: the root is the maximum value in the array, and the left and right subtrees are built recursively from the elements on each side of that maximum. When a new value is appended, it can only affect nodes along the rightmost path of the tree.

Approach 1: Recursive Tree Modification (O(n) time, O(h) space)

This method directly simulates how the tree would change if the new value were appended to the array. Compare val with the current node. If val is greater than the current root, the new value becomes the new root and the previous tree becomes its left child. Otherwise, the insertion must occur somewhere in the right subtree because the value was appended to the end of the array. Recursively process root.right until the correct position is found. The recursion depth equals the tree height h, giving O(n) worst-case time and O(h) space due to the call stack. This approach is clean and closely matches the recursive definition of a tree.

Approach 2: Iterative Approach using Stack (O(n) time, O(n) space)

The iterative solution leverages a monotonic structure similar to how the original maximum binary tree can be built. Traverse the right spine of the tree using a stack to track nodes. While the stack top has a value smaller than val, pop nodes because the new value must become their parent. The last popped node becomes the left child of the new node. If a larger node remains on the stack, attach the new node as its right child. This approach avoids recursion and works well when you want explicit control over traversal. Time complexity is O(n) since each node is pushed and popped at most once, and auxiliary space is O(n). The logic relies on properties of binary tree structure and a monotonic stack.

Recommended for interviews: The recursive modification approach is typically expected because it directly uses the definition of a maximum binary tree and quickly leads to a clean solution. Interviewers often look for the key observation that the insertion only affects the rightmost path. The iterative stack version demonstrates deeper understanding of tree construction patterns and monotonic stacks, which can stand out in more advanced interviews.