Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Binary Tree solution and explanation

MediumArrayBinary TreeDivide and ConquerMonotonic Stack6 min read86.3% acceptanceUpdated 9 Apr 2026
Asked atMicrosoftGoogleMeta
Practise Maximum Binary Tree
11:54
Maximum Binary Tree (LeetCode 654) | Full Solution with a natural way to approach | RecursionNikhil Lohia · 11:54 · 6K viewsWatch on YouTube
9 more videos on this problem
  1. Maximum Binary Tree (LeetCode 654) | Full Solution with a natural way to approach | RecursionNikhil Lohia · 11:54 · 6K views
  2. 花花酱 LeetCode 654. Maximum Binary Tree - 刷题找工作 EP36Hua Hua · 11:11 · 5K views
  3. Maximum Binary Tree - LeetCode Problem #654GuyWho LikesCS · 31:01 · 3K views
  4. LeetCode 654. Maximum Binary TreeGot Up Late · 5:17 · 2K views
  5. 654. Maximum Binary Tree (Leetcode Medium)Programming Live with Larry · 7:47 · 506 views
  6. Construct Max Binary Tree Leetcode 654 c#Sagar Patel · 5:44 · 418 views
  7. Leetcode 654 Maximum Binary Tree Lintcode 1106 · Maximum Binary Tree - Microsoft QuestionAlgorithmicIQ · 9:14 · 398 views
  8. LeetCode 654 | Maximum Binary Tree | Recursion | JavaSleepy Cracker · 3:33 · 393 views
  9. Leetcode 654. Maximum Binary Tree. Recursion.Shen Zheng · 4:09 · 315 views
  10. Leetcode 654 | Maximum Binary Tree | DFSCoding Together · 13:52 · 261 views

The problem

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

  1. Create a root node whose value is the maximum value in nums.
  2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
  3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Example 1:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

Example 2:

Input: nums = [3,2,1]
Output: [3,null,2,null,1]

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • All integers in nums are unique.

Approach overview

Problem Overview: Given an integer array with no duplicates, construct a binary tree where the root is the maximum value in the array. The left subtree is built from elements left of the maximum, and the right subtree from elements on the right. This recursive definition creates what’s called a Maximum Binary Tree.

Approach 1: Recursive Division (Divide and Conquer) (Time: O(n^2) worst, Space: O(n))

The definition of the tree directly suggests a divide and conquer strategy. Scan the current subarray to find the maximum element. Create a node with that value, then recursively build the left subtree from elements before the maximum and the right subtree from elements after it. Each recursive call reduces the problem size until the subarray becomes empty. The drawback is that finding the maximum requires a full scan each time, which leads to O(n^2) time when the array is sorted in decreasing or increasing order. Space complexity is O(n) due to recursion depth and the tree structure.

Approach 2: Monotonic Stack (Time: O(n), Space: O(n))

A more efficient approach uses a monotonic stack. Iterate through the array and maintain a decreasing stack of tree nodes. For each new value, create a node and pop all smaller nodes from the stack. The last popped node becomes the left child of the current node because it is the largest smaller element to its left. If the stack still contains elements, the top node becomes the parent and the current node becomes its right child. Push the current node onto the stack and continue. Each element is pushed and popped at most once, giving linear O(n) time. The stack stores at most n nodes, so space complexity is O(n). This approach constructs the same binary tree without repeatedly scanning subarrays.

Recommended for interviews: Interviewers usually expect the monotonic stack solution because it reduces the naive recursive O(n^2) approach to optimal O(n). Starting with the recursive definition demonstrates understanding of the problem structure, then optimizing with a monotonic stack shows algorithmic maturity and familiarity with common stack patterns.

Approach 1: Recursive Division

Recursive Division Approach: This approach involves breaking down the problem using recursive calls. We start by identifying the maximum element in the array, which becomes the root of the tree. We then recursively split the array into sub-arrays on the left and right of the maximum element and construct the left and right subtrees respectively. This leverages the divide-and-conquer paradigm.

from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        max_idx = nums.index(max(nums))
        root = TreeNode(nums[max_idx])
        root.left = self.constructMaximumBinaryTree(nums[:max_idx])
        root.right = self.constructMaximumBinaryTree(nums[max_idx + 1:])
        return root
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length);
    }
    private TreeNode construct(int[] nums, int left, int right) {
        if (left == right) return null;
        int maxIndex = left;
        for (int i = left + 1; i < right; i++) {
            if (nums[i] > nums[maxIndex]) maxIndex = i;
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = construct(nums, left, maxIndex);
        root.right = construct(nums, maxIndex + 1, right);
        return root;
    }
}
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    if (nums.empty()) return NULL;
    auto max_it = max_element(nums.begin(), nums.end());
    TreeNode* root = new TreeNode(*max_it);
    vector<int> left(nums.begin(), max_it);
    vector<int> right(max_it + 1, nums.end());
    root->left = constructMaximumBinaryTree(left);
    root->right = constructMaximumBinaryTree(right);
    return root;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var constructMaximumBinaryTree = function(nums) {
    if (nums.length === 0) return null;
    const maxIndex = nums.reduce((maxIdx, num, idx) => num > nums[maxIdx] ? idx : maxIdx, 0);
    const root = new TreeNode(nums[maxIndex]);
    root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
    root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
    return root;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    if (numsSize == 0) return NULL;
    int maxIdx = 0;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > nums[maxIdx]) maxIdx = i;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[maxIdx];
    root->left = constructMaximumBinaryTree(nums, maxIdx);
    root->right = constructMaximumBinaryTree(nums + maxIdx + 1, numsSize - maxIdx - 1);
    return root;
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        return Construct(nums, 0, nums.Length);
    }

    private TreeNode Construct(int[] nums, int left, int right) {
        if (left == right) return null;
        int maxIndex = left;
        for (int i = left + 1; i < right; i++) {
            if (nums[i] > nums[maxIndex]) maxIndex = i;
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = Construct(nums, left, maxIndex);
        root.right = Construct(nums, maxIndex + 1, right);
        return root;
    }
}

This Python solution constructs the maximum binary tree using Pyhton lists and recursion. max function is used to determine the maximum element's index, and slicing helps in defining the subarrays for left and right children, thereby recursively constructing the tree nodes.

Complexity

Time Complexity: O(n^2) as the max calculation is O(n) and done n times. Space Complexity: O(n) due to list slices and recursion depth.

Try this approach in the editor

Approach 2: Monotonic Stack

Monotonic Stack Approach: This approach involves utilizing a stack to directly simulate the necessary operations required to construct the maximum binary tree without recursion. By pushing and popping elements based on comparisons with the current element, we maintain a monotonic sequence from which the tree is constructed. This method leverages the stack to ensure that nodes are connected efficiently without the overhead of recursive calls.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def constructMaximumBinaryTree(self, nums):
        stack = []
        for num in nums:
            current = TreeNode(num)
            while stack and stack[-1].val < num:
                current.left = stack.pop()
            if stack:
                stack[-1].right = current
            stack.append(current)
        return stack[0]
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Stack<TreeNode> stack = new Stack<>();
        for (int num : nums) {
            TreeNode curr = new TreeNode(num);
            while (!stack.isEmpty() && stack.peek().val < num) {
                curr.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = curr;
            }
            stack.push(curr);
        }
        while (stack.size() > 1) stack.pop();
        return stack.pop();
    }
}
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    stack<TreeNode*> stk;
    for (int num : nums) {
        TreeNode* current = new TreeNode(num);
        while (!stk.empty() && stk.top()->val < num) {
            current->left = stk.top();
            stk.pop();
        }
        if (!stk.empty()) {
            stk.top()->right = current;
        }
        stk.push(current);
    }
    while (stk.size() > 1) stk.pop();
    return stk.top();
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var constructMaximumBinaryTree = function(nums) {
    const stack = [];
    for (const num of nums) {
        const current = new TreeNode(num);
        while (stack.length > 0 && stack[stack.length - 1].val < num) {
            current.left = stack.pop();
        }
        if (stack.length > 0) {
            stack[stack.length - 1].right = current;
        }
        stack.push(current);
    }
    return stack[0];
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * numsSize);
    int stackSize = 0;
    for (int i = 0; i < numsSize; ++i) {
        struct TreeNode* current = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        current->val = nums[i];
        current->left = NULL;
        current->right = NULL;
        while (stackSize > 0 && stack[stackSize - 1]->val < nums[i]) {
            current->left = stack[stackSize - 1];
            stackSize--;
        }
        if (stackSize > 0) {
            stack[stackSize - 1]->right = current;
        }
        stack[stackSize++] = current;
    }
    while (stackSize > 1) {
        stackSize--;
    }
    struct TreeNode* root = stack[0];
    free(stack);
    return root;
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        foreach (int num in nums) {
            TreeNode current = new TreeNode(num);
            while (stack.Count > 0 && stack.Peek().val < num) {
                current.left = stack.Pop();
            }
            if (stack.Count > 0) {
                stack.Peek().right = current;
            }
            stack.Push(current);
        }
        while (stack.Count > 1) stack.Pop();
        return stack.Pop();
    }
}

Description: This Python version uses a stack to maintain the tree structure as the list is processed. Each number is made the current node, and nodes are popped from the stack and linked as left children if they are smaller, leveraging stack properties to form the required structure.

Complexity

Time Complexity: O(n) facilitated by single traversal and using a stack. Space Complexity: O(n) due to stack storage requirements for tree construction.

Try this approach in the editor

Approach 3: Default Approach

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    const n = nums.length;
    if (n === 0) {
        return null;
    }
    const [val, i] = nums.reduce((r, v, i) => (r[0] < v ? [v, i] : r), [-1, 0]);
    return new TreeNode(
        val,
        constructMaximumBinaryTree(nums.slice(0, i)),
        constructMaximumBinaryTree(nums.slice(i + 1)),
    );
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
	var dfs func(l, r int) *TreeNode
	dfs = func(l, r int) *TreeNode {
		if l > r {
			return nil
		}
		i := l
		for j := l; j <= r; j++ {
			if nums[i] < nums[j] {
				i = j
			}
		}
		root := &TreeNode{Val: nums[i]}
		root.Left = dfs(l, i-1)
		root.Right = dfs(i+1, r)
		return root
	}
	return dfs(0, len(nums)-1)
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn construct(nums: &Vec<i32>, start: usize, end: usize) -> Option<Rc<RefCell<TreeNode>>> {
        if start >= end {
            return None;
        }
        let mut idx = 0;
        let mut max_val = -1;
        for i in start..end {
            if nums[i] > max_val {
                idx = i;
                max_val = nums[i];
            }
        }
        Some(Rc::new(RefCell::new(TreeNode {
            val: max_val,
            left: Self::construct(nums, start, idx),
            right: Self::construct(nums, idx + 1, end),
        })))
    }

    pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::construct(&nums, 0, nums.len())
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Division

Time Complexity: O(n^2) as the max calculation is O(n) and done n times. Space Complexity: O(n) due to list slices and recursion depth.

Monotonic Stack

Time Complexity: O(n) facilitated by single traversal and using a stack. Space Complexity: O(n) due to stack storage requirements for tree construction.

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive Division (Divide and Conquer)O(n^2) worst caseO(n)Good for understanding the recursive definition of the tree and for quick implementation in interviews
Monotonic StackO(n)O(n)Optimal solution when building the tree efficiently from a single array pass

Frequently asked questions

Is Maximum Binary Tree easy or hard?

Maximum Binary Tree is rated Medium difficulty on LeetCode. The recursive solution is straightforward once the definition is understood, but identifying and implementing the optimal monotonic stack solution requires stronger algorithmic insight.

Maximum Binary Tree Python/Java solution

Python and Java implementations typically follow either recursive divide and conquer or the monotonic stack approach. The recursive version is shorter and closely mirrors the problem definition, while the stack-based version achieves optimal O(n) time and is preferred for large inputs.

How to solve Maximum Binary Tree in O(n)?

Use a monotonic decreasing stack. Iterate through the array, popping smaller elements and assigning them as the left child of the current node. If a larger element remains on the stack, it becomes the parent and the current node becomes its right child. Each element is pushed and popped once, resulting in linear O(n) time.

What is the best approach for Maximum Binary Tree?

The optimal approach uses a monotonic decreasing stack. It processes the array once and links nodes while maintaining decreasing order, ensuring each element is pushed and popped at most once. This builds the same tree as the recursive definition but runs in O(n) time with O(n) space.

Is Maximum Binary Tree asked at Google/Amazon/Meta?

Maximum Binary Tree is a classic stack and tree construction problem commonly seen in coding interviews at companies like Amazon and Google. It tests understanding of divide and conquer, monotonic stacks, and binary tree construction from arrays.

What data structure is used in Maximum Binary Tree?

The key data structures are binary trees and stacks. The recursive solution relies on divide and conquer to build the tree, while the optimized solution uses a monotonic stack to determine parent-child relationships efficiently.

What is the time complexity of Maximum Binary Tree?

The divide and conquer approach has O(n^2) worst-case time because each recursive call scans the remaining subarray to find the maximum. The optimized monotonic stack solution reduces this to O(n) time since each element is processed once. Space complexity for both approaches is O(n).

Comments

Next problem · similarMaximum Binary Tree IIMedium
Now write it yourselfClose this page and solve Maximum Binary Tree in the editor, without looking.
Practise Maximum Binary Tree