Maximum Binary Tree

MediumDivide & Conquer · Monotonic Stack🧩 Recursion & Divide and Conquer LeetCode #654 ↗Updated Oct 30, 2026

Problem

You get an array nums of distinct integers. Build a tree recursively: the largest value becomes the root, the elements to its left in the array form the left subtree (built the same way), and the elements to its right form the right subtree. Return the root.

Input[4,7,1,5,2]Output[7,4,5,null,null,1,2]

Input[1,2,3]Output[3,2,null,1]

Input[9]Output[9]

1 ≤ n ≤ 1000 · 0 ≤ nums[i] ≤ 1000 · all values distinct

Try it yourself

Java

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A node's parent is the smaller of its nearest greater element on the left and on the right. A decreasing stack finds both in one sweep: the nodes a new value pops become its left child, and it becomes the right child of whatever remains on top.

PatternRecursion & Divide and Conquer

Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.

Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.

Open the Recursion & Divide and Conquer guide →

Approaches

Brute ForceDirect Recursion with Linear Max Scan

Time O(n²)Space O(n)

Follow the definition literally: scan [lo, hi] for the max, make it the root, recurse on both sides. Each level of recursion scans its whole range, so a sorted array (a chain-shaped tree) costs n + (n-1) + … scans.

Java

public TreeNode constructMaximumBinaryTree(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int maxIdx = lo;
    for (int i = lo + 1; i <= hi; i++) {
        if (nums[i] > nums[maxIdx]) maxIdx = i;
    }
    TreeNode root = new TreeNode(nums[maxIdx]);
    root.left = build(nums, lo, maxIdx - 1);
    root.right = build(nums, maxIdx + 1, hi);
    return root;
}

Mirrors the statement; quadratic on sorted input, O(n log n) on random input.

BetterRecursion + Sparse Table Range-Max

Time O(n log n)Space O(n log n)

The only slow part is “index of the max in [lo, hi]”. Precompute a sparse table where sp[k][i] is the argmax of the window of length 2^k starting at i; any range is covered by two overlapping windows, so each query is O(1). Building the table dominates.

Java

private int[][] sp;
private int[] nums;
public TreeNode constructMaximumBinaryTree(int[] nums) {
    this.nums = nums;
    int n = nums.length, levels = 1;
    while ((1 << levels) <= n) levels++;
    sp = new int[levels][n];
    for (int i = 0; i < n; i++) sp[0][i] = i;
    for (int k = 1; k < levels; k++) {
        for (int i = 0; i + (1 << k) <= n; i++) {
            int a = sp[k - 1][i], b = sp[k - 1][i + (1 << (k - 1))];
            sp[k][i] = nums[a] > nums[b] ? a : b;
        }
    }
    return build(0, n - 1);
}
private int argMax(int lo, int hi) { // two overlapping power-of-two windows
    int k = 31 - Integer.numberOfLeadingZeros(hi - lo + 1);
    int a = sp[k][lo], b = sp[k][hi - (1 << k) + 1];
    return nums[a] > nums[b] ? a : b;
}
private TreeNode build(int lo, int hi) {
    if (lo > hi) return null;
    int m = argMax(lo, hi);
    TreeNode root = new TreeNode(nums[m]);
    root.left = build(lo, m - 1);
    root.right = build(m + 1, hi);
    return root;
}

Guaranteed O(n log n), but extra table memory and code just to answer range-max.

OptimalMonotonic Decreasing Stack

Time O(n)Space O(n)

Process values left to right keeping a stack of nodes with decreasing values (the current “right spine”). A new node pops every smaller node; the last one popped is the max of the run just left of it, so it becomes the new node's left child. The node left on top (if any) is bigger, so the new node hangs as its right child. Each node is pushed and popped once.

Java

public TreeNode constructMaximumBinaryTree(int[] nums) {
    Deque<TreeNode> stack = new ArrayDeque<>(); // values decrease bottom -> top
    for (int x : nums) {
        TreeNode node = new TreeNode(x);
        TreeNode lastPopped = null;
        while (!stack.isEmpty() && stack.peek().val < x) {
            lastPopped = stack.pop();
        }
        node.left = lastPopped;               // biggest of the smaller run on the left
        if (!stack.isEmpty()) stack.peek().right = node; // nearest bigger on the left
        stack.push(node);
    }
    return stack.peekLast(); // bottom of the stack = global max
}

Linear and iterative — no recursion depth issues on sorted input.

Pro tip

A later, bigger value may overwrite peek().right — that's correct: the old right child gets re-attached as someone's left child.

At a glance

Level	Approach	Time	Space
Brute Force	Direct Recursion with Linear Max Scan	`O(n²)`	`O(n)`
Better	Recursion + Sparse Table Range-Max	`O(n log n)`	`O(n log n)`
Optimal	Monotonic Decreasing Stack	`O(n)`	`O(n)`

Common pitfalls

Returning stack.peek() (the top) — the root is at the bottom.
Attaching every popped node as the left child — only the last popped one is.
Assuming the recursion is always O(n log n) — sorted input makes it O(n²).

Interview tips

Code the recursive definition first; it's short and clearly correct.
Point out the worst case (sorted input) to motivate a faster range-max or the stack.
Explain the stack via “parent = smaller of the two nearest greater neighbours”.

Pattern

Monotonic stack / Cartesian tree → build or query structure defined by nearest greater (or smaller) elements.

My notes saved in this browser