Maximum Binary Tree II — Solution in Python, Java & C++
Maximum Binary Tree II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.
Maximum Binary Tree II is a medium coding problem on binary search and trees, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Binary Search, Trees
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A maximum tree is built from an array a of distinct values: its root holds the maximum of a, the left subtree is the maximum tree of the elements before that maximum, and the right subtree the maximum tree of the elements after it (an empty part gives an empty subtree).
You are given the root of the maximum tree of some array a — but not a itself — and an integer value that does not occur in a. Let b be a with value appended at the end. Return the root of the maximum tree of b.
Example 1
Input: root = [4,1,3,null,null,2], value = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: The tree was built from [1,4,2,3]; the new array [1,4,2,3,5] has 5 as its maximum, at the very end, so 5 becomes the root with the old tree as its left subtree.
Example 2
Input: root = [5,2,4,null,1], value = 3
Output: [5,2,4,null,1,null,3]
Explanation: Built from [2,1,5,4]; appending 3 gives [2,1,5,4,3], where 3 ends up as the right child of 4.
Example 3
Input: root = [5,2,3,null,1], value = 4
Output: [5,2,4,null,1,3]
Explanation: Built from [2,1,5,3]; in [2,1,5,3,4] the 4 sits right of 5 and takes 3 as its left child.
Constraints
The number of nodes in the tree is in the range [1, 100]1 <= Node.val <= 100All the values of the tree are unique1 <= value <= 100value does not occur in the tree
Hints for Maximum Binary Tree II
Hint 1
The new element is the last one of
b. Where does the last element of an array end up in its maximum tree?Hint 2
If
valueis larger than the root, it is the new maximum and everything before it is its left part: a new root with the old tree on the left.Hint 3
Otherwise the root stays, and
valuebelongs to the part after the root's position — that part is the root's right subtree. Recurse to the right.
How to solve Maximum Binary Tree II
Appending at the end only touches the right spine of the tree, which holds the suffix maxima of a. Walk down that spine until a node smaller than value (or the end) is reached; value takes that position and adopts the rest of the spine as its left subtree.
Approach
- If
rootis null orroot.val < value, return a new node holdingvaluewhose left child isroot. - Otherwise set
root.right = insertIntoMaxTree(root.right, value)and returnroot.
Why it works
The root's position in b is unchanged when root.val > value, and value falls in the part after it, which is exactly the root's right subtree built from that suffix plus value — the same problem, smaller. When value exceeds the current subtree's maximum, it is the maximum of that range in b; since it is the last element, everything else in the range lies to its left, which is precisely the old subtree.
Complexity
- Time —
O(h) — one walk down the right spine - Space —
O(h) for the recursion (O(1) iteratively)
Pitfalls
- Only the right spine can change: never descend into a left subtree.
- When
valueis the overall maximum, the entire old tree becomes its left subtree. - Rebuilding the whole tree from the in-order array also works but costs O(n^2).
Reference solution
Python
from typing import Optional
def insertIntoMaxTree(root: Optional[TreeNode], value: int) -> Optional[TreeNode]:
if root is None or root.val < value:
return TreeNode(value, root, None)
root.right = insertIntoMaxTree(root.right, value)
return rootJava
public static TreeNode insertIntoMaxTree(TreeNode root, int value) {
if (root == null || root.val < value) return new TreeNode(value, root, null);
root.right = insertIntoMaxTree(root.right, value);
return root;
}C++
TreeNode* insertIntoMaxTree(TreeNode* root, int value) {
if (!root || root->val < value) return new TreeNode(value, root, nullptr);
root->right = insertIntoMaxTree(root->right, value);
return root;
}JavaScript
var insertIntoMaxTree = function(root, value) {
if (root === null || root.val < value) return new TreeNode(value, root, null);
root.right = insertIntoMaxTree(root.right, value);
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 189 binary search problems · the whole catalogue
Learn the technique: Binary Search · Binary Trees and Tree Traversals