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, the given tree was constructed from a list a (root = Construct(a)) recursively with the following Construct(a) routine:
a is empty, return null.a[i] be the largest element of a. Create a root node with the value a[i].root will be Construct([a[0], a[1], ..., a[i - 1]]).root will be Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]).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:
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:
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:
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:
[1, 100].1 <= Node.val <= 1001 <= val <= 100Problem 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.
This approach involves recursively inserting the new value into the correct position in the maximum binary tree. The main idea is to find the correct place in the tree for the new value by comparing it with the current node values as we traverse the tree from top to bottom.
If the new value is greater than the root node, the new value becomes the new root, and the entire existing tree becomes its left subtree. Otherwise, recursively consider this insertion as a problem for the root's right subtree, as all existing left-side nodes are already smaller than the current root.
We define a TreeNode class to represent each node in the tree. The insertIntoMaxTree function accepts the root of the tree and an integer val. If the root is null (empty tree) or the val is greater than the root's value, we make val the new root node with the current root as its left child. Otherwise, we recursively try to insert val into the right subtree.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(n) in the worst case due to the recursion stack.
This approach attempts to solve the problem using an iterative method with the help of a stack to simulate the recursive behavior. As the new value is only appended to the right-most part of the implied array, we have to check from right to left in the tree structure to find the appropriate place for the new value to maintain the maximum tree property.
The main idea is to traverse the right nodes of the tree using a stack until we find the correct position for the new node.
This solution uses a loop instead of a recursive approach to insert the node. We iterate down the chain of right children until we find a spot where the new node should be inserted. This will involve attaching the new node's left subtree as the right child of the current node.
Java
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(1) since additional structures (e.g., a stack) are not used.
If val is the maximum number, then make val the new root node, and root the left subtree of the new root node.
If val is not the maximum number, since val is the last appended number, it must be on the right side of root. Therefore, we can insert val as a new node into the right subtree of root.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the tree.
Search the right subtree, find the node where curr.val \gt val \gt curr.right.val, then create a new node node, point node.left to curr.right, and then point curr.right to node.
Finally, return root.
The time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Tree Modification | Time Complexity: O(n), where |
| Iterative Approach using Stack | Time Complexity: O(n), where |
| Recursion | — |
| Iteration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Modification | O(n) | O(h) | Best general solution. Clean logic and closely follows the definition of a maximum binary tree. |
| Iterative Stack Approach | O(n) | O(n) | Useful when avoiding recursion or when applying monotonic stack patterns. |
998. Maximum Binary Tree II • Muerde un zombie • 363 views views
Watch 9 more video solutions →Practice Maximum Binary Tree II with our built-in code editor and test cases.
Practice on FleetCode