You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
nums.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] <= 1000nums are unique.The Maximum Binary Tree is built from an array where the root is the maximum element, the left subtree is built from elements to the left of the maximum, and the right subtree is built from elements to the right. A natural way to approach this is using divide and conquer. Find the maximum element in the current range, create a node, then recursively build the left and right subtrees. While simple and intuitive, repeatedly scanning for the maximum can increase the runtime in worst cases.
A more optimized strategy uses a monotonic decreasing stack. As you iterate through the array, maintain a stack where elements remain in decreasing order. When a larger element appears, pop smaller elements and attach them as the left child of the current node. The remaining stack top becomes the parent, connecting the current node as its right child. This technique constructs the tree in a single pass.
The stack-based approach achieves O(n) time complexity, while the recursive divide-and-conquer method can degrade to O(n²) in the worst case.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Divide and Conquer (Recursive) | O(n^2) worst case, O(n log n) average | O(n) recursion stack |
| Monotonic Stack | O(n) | O(n) |
NeetCode
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of Maximum Binary Tree appear in technical interviews at large tech companies. Interviewers use it to test understanding of stacks, tree construction, and divide-and-conquer strategies.
The optimal approach uses a monotonic decreasing stack. By processing each element once and maintaining stack order, the binary tree can be constructed in linear time without repeatedly searching for maximum values.
The monotonic stack ensures elements are processed in decreasing order, making it easy to identify parent-child relationships. This avoids repeated scans for maximum elements and reduces the overall time complexity to O(n).
A monotonic stack is the most efficient data structure for this problem. It helps maintain decreasing order and allows quick attachment of left and right child relationships while building the tree.
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.