Maximum Binary Tree II
MedPrompt
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:
- If
ais empty, returnnull. - Otherwise, let
a[i]be the largest element ofa. Create arootnode with the valuea[i]. - The left child of
rootwill beConstruct([a[0], a[1], ..., a[i - 1]]). - The right child of
rootwill beConstruct([a[i + 1], a[i + 2], ..., a[a.length - 1]]). - Return
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:
- The number of nodes in the tree is in the range
[1, 100]. 1 <= Node.val <= 100- All the values of the tree are unique.
1 <= val <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach follows a straightforward, brute-force method. First, it reconstructs the original array a from which the given maximum binary tree was built. Then, it appends the new value val to this array to form a new array b. Finally, it constructs a new maximum binary tree from the array b using the standard construction algorithm.
Algorithm
- Create an empty list, say
a. - Perform an in-order traversal on the input tree
root. During the traversal, add each visited node's value to the lista. - Append the given
valto the lista. - Construct a new maximum binary tree from the modified list
ausing the recursive construction algorithm. - Return the root of the newly constructed tree.
Walkthrough
The core idea is to reverse the construction process to get the original data, modify the data, and then re-apply the construction process.
Step 1: Reconstruct the original array a. A key property of the maximum binary tree is that an in-order traversal of the tree yields the original array a. We perform an in-order traversal on the given root and store the node values in a list.
Step 2: Append val to form b. After obtaining the list a, we simply append the new integer val to it to get the list b.
Step 3: Construct the new tree from b. We implement the Construct(b) routine as described in the problem. This function recursively finds the maximum element in the current segment of the array, creates a root with it, and then builds the left and right subtrees from the parts of the array to the left and right of the maximum element.
class Solution { public TreeNode insertIntoMaxTree(TreeNode root, int val) { List<Integer> a = new ArrayList<>(); inorder(root, a); a.add(val); return construct(a, 0, a.size() - 1); } private void inorder(TreeNode node, List<Integer> list) { if (node == null) { return; } inorder(node.left, list); list.add(node.val); inorder(node.right, list); } private TreeNode construct(List<Integer> nums, int left, int right) { if (left > right) { return null; } int maxIndex = -1; int maxVal = -1; for (int i = left; i <= right; i++) { if (nums.get(i) > maxVal) { maxVal = nums.get(i); maxIndex = i; } } TreeNode node = new TreeNode(maxVal); node.left = construct(nums, left, maxIndex - 1); node.right = construct(nums, maxIndex + 1, right); return node; }}Complexity
Time
O(N^2), where N is the number of nodes in the original tree. The in-order traversal takes O(N). The construction of the new tree from an array of size N+1 takes O((N+1)^2) because for each node, we scan a subarray to find the maximum.
Space
O(N). We need O(N) space to store the array `a` (and `b`). The recursion stack for both traversal and construction can go up to O(N) in the case of a skewed tree.
Trade-offs
Pros
Conceptually simple and easy to understand.
Directly simulates the problem definition.
Cons
Highly inefficient. It rebuilds the entire tree from scratch, even though the change is localized.
Requires significant extra space to store the intermediate array.
This approach leverages the properties of the maximum binary tree construction. Since val is appended to the original array a, it will always be in the 'right part' of the array relative to any existing element. This means we only need to consider inserting val into the right spine of the tree. A recursive function can elegantly handle this insertion.
Algorithm
- Define a function
insertIntoMaxTree(root, val). - Base Case: If
rootisnull, return a newTreeNode(val). - If
val > root.val,valbecomes the new root. The originalrootbecomes the left child of the new node. CreatenewRoot = new TreeNode(val), setnewRoot.left = root, and returnnewRoot. - If
val < root.val,valmust be inserted into the right subtree. Recursively callinsertIntoMaxTreeon the right child:root.right = insertIntoMaxTree(root.right, val). - Return the
root.
Walkthrough
The logic is based on where val fits in the construction of b = a + [val]. The main function itself can serve as the recursive function.
-
Base Case: If
rootisnull, it means we've reached a point where a new subtree needs to be created. The list that would form this subtree is empty, and we are addingval.Construct([val])is simply a new node withval. So, we returnnew TreeNode(val). -
Recursive Step 1: If
val > root.val. According to the construction rule,valis the new maximum for the list that formed the subtree atroot. The new root will be a node withval. The entire original tree was formed from a list that is now entirely to the left ofval. Therefore, the originalrootbecomes the left child of the new node. The right child isnull. We returnnew TreeNode(val, root, null). -
Recursive Step 2: If
val < root.val. The root of the current subtree (root) does not change. The new valuevalmust belong to the right part of the list relative toroot.val. Therefore, we need to insertvalinto the right subtree ofroot. We do this by making a recursive call:root.right = insertIntoMaxTree(root.right, val). We then return the (unmodified)root.
class Solution { public TreeNode insertIntoMaxTree(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } if (val > root.val) { TreeNode newRoot = new TreeNode(val); newRoot.left = root; return newRoot; } root.right = insertIntoMaxTree(root.right, val); return root; }}Complexity
Time
O(H), where H is the height of the tree. In the worst case (a skewed tree), the height is O(N), making the time complexity O(N). We only traverse down the right spine.
Space
O(H) due to the recursion stack, where H is the height of the tree. In the worst case of a skewed tree, this is O(N).
Trade-offs
Pros
Much more efficient than rebuilding the tree.
The logic directly follows the recursive definition of the tree construction.
The code is very concise and elegant.
Cons
Uses recursion, which can lead to a
StackOverflowErrorfor very deep trees (not an issue with the given constraints).The space complexity is dependent on the tree's height.
This approach is an iterative optimization of the recursive solution. It avoids the recursion stack overhead by using a loop. The logic remains the same: since val is appended to the original array, we only need to find its correct position along the right spine of the tree.
Algorithm
- Create a new node
newNodewith the valueval. - If
rootisnullorval > root.val, setnewNode.left = rootand returnnewNode. - Initialize a pointer
curr = root. - Traverse down the right spine of the tree: while
curr.rightis notnullandcurr.right.valis greater thanval, updatecurr = curr.right. - After the loop,
curris the parent node for the new subtree. - Set
newNode.lefttocurr.right(attaching the rest of the right spine). - Set
curr.righttonewNode. - Return the original
root.
Walkthrough
This method achieves the same result as the recursive one but with constant extra space.
-
Case 1:
valis the new maximum. Ifval > root.val,valbecomes the new root of the entire tree. The original tree becomes the left child of the new node. We createnew TreeNode(val, root, null)and return it. This is the same as the recursive approach. -
Case 2:
valis not the new maximum. Ifval < root.val, the root of the tree remains unchanged. We knowvalmust be inserted somewhere in the right subtree. We need to find the first node on the right spine that is smaller thanval. -
We start at the
rootand traverse down its right children. Letcurrbe the current node. -
We keep moving to the right child (
curr = curr.right) as long as the right child exists and its value is greater thanval. -
The loop
while (curr.right != null && curr.right.val > val)finds the nodecurrwhich will be the parent of the new subtree containingval. -
Once the loop terminates,
curris the node whose right child will be replaced. The originalcurr.rightsubtree (which is eithernullor has a value less thanval) will become the left child of the new node withval.
class Solution { public TreeNode insertIntoMaxTree(TreeNode root, int val) { TreeNode newNode = new TreeNode(val); if (root == null || val > root.val) { newNode.left = root; return newNode; } TreeNode curr = root; while (curr.right != null && curr.right.val > val) { curr = curr.right; } newNode.left = curr.right; curr.right = newNode; return root; }}Complexity
Time
O(H), where H is the height of the tree. In the worst case (a skewed tree), this is O(N). The traversal is limited to the right spine of the tree.
Space
O(1). We only use a few pointers (`curr`, `newNode`), so the extra space is constant.
Trade-offs
Pros
Optimal time complexity for this problem.
Optimal space complexity (O(1) extra space).
Avoids recursion, making it safe for very deep trees.
Cons
The iterative logic might be slightly less intuitive to come up with compared to the direct recursive translation.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode insertIntoMaxTree ( TreeNode root , int val ) { if ( root == null || root . val < val ) { return new TreeNode ( val , root , null ); } root . right = insertIntoMaxTree ( root . right , val ); return root ; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * insertIntoMaxTree ( TreeNode * root , int val ) { if ( ! root || root -> val < val ) return new TreeNode ( val , root , nullptr ); root -> right = insertIntoMaxTree ( root -> right , val ); return root ; } };# 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 root is None or root . val < val : return TreeNode ( val , root ) root . right = self . insertIntoMaxTree ( root . right , val ) return rootVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.