Maximum Binary Tree - Solution & Explanation
Problem Statement
You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
- Create a root node whose value is the maximum value in
nums. - Recursively build the left subtree on the subarray prefix to the left of the maximum value.
- 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 <= 10000 <= nums[i] <= 1000- All integers in
numsare 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.
This C implementation uses a recursive function to build the maximum binary tree. The base case checks if the array is empty, returning NULL for the node. It finds the index of the maximum value, which becomes the root node's value, and then recursively builds the left and right subtrees from the elements to the left and right of this value.
Complexity
Time Complexity: O(n^2), where n is the number of elements, due to the repeated search for the maximum element. Space Complexity: O(n) for the recursion stack.
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.
Description: This C solution uses a monotonic stack to keep track of nodes. As we iterate over the elements, we maintain the condition where each parent node's right child points to the current node, while popping off smaller elements and assigning them as left children.
Complexity
Time Complexity: O(n), where n is the number of elements, ensured by single pass and stack operations. Space Complexity: O(n) due to stack storage.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Division | Time Complexity: O(n^2), where n is the number of elements, due to the repeated search for the maximum element. Space Complexity: O(n) for the recursion stack. |
| Monotonic Stack | Time Complexity: O(n), where n is the number of elements, ensured by single pass and stack operations. Space Complexity: O(n) due to stack storage. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Division (Divide and Conquer) | O(n^2) worst case | O(n) | Good for understanding the recursive definition of the tree and for quick implementation in interviews |
| Monotonic Stack | O(n) | O(n) | Optimal solution when building the tree efficiently from a single array pass |
Video Solution
Maximum Binary Tree (LeetCode 654) | Full Solution with a natural way to approach | Recursion • Nikhil Lohia • 6,283 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Binary Tree easy or hard?
Maximum Binary Tree Python/Java solution
How to solve Maximum Binary Tree in O(n)?
What is the best approach for Maximum Binary Tree?
Is Maximum Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Maximum Binary Tree?
What is the time complexity of Maximum Binary Tree?
Ready to solve this problem?
Practice Maximum Binary Tree with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor