Maximum Binary Tree

Medium
1925.

Maximum Binary Tree

Maximum Binary Tree is a medium coding problem on arrays, trees and stack, asked in Amazon and Microsoft interviews.

You are given an integer array nums with no duplicates. Its maximum binary tree is built recursively:

  1. The root holds the maximum value in nums.
  2. The left subtree is the maximum binary tree of the elements to the left of that maximum.
  3. 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 <= 1000
  • 0 <= nums[i] <= 1000
  • All 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)?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

Problem statement

You are given an integer array nums with no duplicates. Its maximum binary tree is built recursively:

  1. The root holds the maximum value in nums.
  2. The left subtree is the maximum binary tree of the elements to the left of that maximum.
  3. 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 <= 1000
  • 0 <= nums[i] <= 1000
  • All 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

  1. 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.

  2. 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…

  3. 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

  1. Keep a stack of nodes whose values decrease from bottom to top.
  2. For each value x, create its node. Pop every node smaller than x; the last one popped becomes the new node's left child.
  3. 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).
  4. 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