Maximum Binary Tree — Solution in Python, Java & C++
Maximum Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and trees.
Maximum Binary Tree is a medium coding problem on arrays, trees and stack, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Trees, Stack, Monotonic Stack, Divide and Conquer
- Asked at: Amazon, Microsoft
- 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
You are given an integer array nums with no duplicates. Its maximum binary tree is built recursively:
- The root holds the maximum value in
nums. - The left subtree is the maximum binary tree of the elements to the left of that maximum.
- The right subtree is the maximum binary tree of the elements to the right of that maximum.
An empty range gives an empty subtree. Build the maximum binary tree of nums and return its root.
Example 1
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: 6 is the maximum, so it is the root; [3,2,1] builds its left subtree (3 with the chain 2 → 1 to its right) and [0,5] its right subtree (5 with 0 to its left).
Example 2
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
Explanation: Each maximum is the first element of what remains, so every node hangs to the right of the previous one.
Example 3
Input: nums = [1,2,3]
Output: [3,2,null,1]
Explanation: Now each maximum is the last element, so the tree leans left.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 1000All integers in nums are unique
Follow-up: The direct recursion is O(n^2) on a sorted array. Can you build the tree in O(n)?
Hints for Maximum Binary Tree
Hint 1
The definition is already an algorithm: find the maximum, split around it, recurse on both sides. That is O(n^2) in the worst case.
Hint 2
Process the array left to right and think about where each new element ends up: it becomes the right child of the nearest greater element to its left…
Hint 3
…and the chain of smaller elements just before it becomes its left subtree. A stack kept in decreasing order holds exactly the candidates.
How to solve Maximum Binary Tree
In the maximum tree, each element's parent is the smaller of its nearest greater neighbour on the left and on the right. A monotonic decreasing stack finds those neighbours in one left-to-right pass and wires up the links as it goes.
Approach
- Keep a stack of nodes whose values decrease from bottom to top.
- For each value
x, create its node. Pop every node smaller thanx; the last one popped becomes the new node's left child. - If the stack is not empty afterwards, the new node becomes the right child of the node on top (the nearest greater element to its left).
- Push the new node. When the array ends, the bottom of the stack is the root.
Why it works
The popped nodes form a decreasing run of smaller elements immediately to the left of x, and the largest of them (the last popped) is the maximum of the range between x and its nearest greater left neighbour — exactly x's left subtree root. The node left on top is greater than x and nearer than any other greater element, and any later right child it takes is replaced only by an element larger than x, which then adopts x on its left. The global maximum is never popped, so it ends at the bottom.
Complexity
- Time —
O(n) — every node is pushed and popped at most once - Space —
O(n) for the stack
Pitfalls
- Setting the right child of the stack's top must happen after the pops; it overwrites a right child that has just been moved into the new node's left subtree.
- The root is the bottom of the stack, not the top.
- The plain recursion is fine for small inputs but degrades to O(n^2) on sorted arrays.
Reference solution
Python
from typing import List, Optional
def constructMaximumBinaryTree(nums: List[int]) -> Optional[TreeNode]:
stack = []
for x in nums:
node = TreeNode(x)
last = None
while stack and stack[-1].val < x:
last = stack.pop()
node.left = last
if stack:
stack[-1].right = node
stack.append(node)
return stack[0]Java
public static TreeNode constructMaximumBinaryTree(int[] nums) {
ArrayList<TreeNode> stack = new ArrayList<>();
for (int x : nums) {
TreeNode node = new TreeNode(x);
TreeNode last = null;
while (!stack.isEmpty() && stack.get(stack.size() - 1).val < x) last = stack.remove(stack.size() - 1);
node.left = last;
if (!stack.isEmpty()) stack.get(stack.size() - 1).right = node;
stack.add(node);
}
return stack.get(0);
}C++
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
vector<TreeNode*> stack;
for (int x : nums) {
TreeNode* node = new TreeNode(x);
TreeNode* last = nullptr;
while (!stack.empty() && stack.back()->val < x) {
last = stack.back();
stack.pop_back();
}
node->left = last;
if (!stack.empty()) stack.back()->right = node;
stack.push_back(node);
}
return stack[0];
}JavaScript
var constructMaximumBinaryTree = function(nums) {
var stack = [];
for (var i = 0; i < nums.length; i++) {
var node = new TreeNode(nums[i]);
var last = null;
while (stack.length > 0 && stack[stack.length - 1].val < nums[i]) last = stack.pop();
node.left = last;
if (stack.length > 0) stack[stack.length - 1].right = node;
stack.push(node);
}
return stack[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Trees and Tree Traversals