Maximum Binary Tree

Med

#0608Time: O(n^2) in the worst case. For each node created, we might scan a large portion of the array to find the next maximum. In the worst case (a sorted array), the work done is proportional to `n + (n-1) + ... + 1`, which is O(n^2). The average case is O(n log n).Space: O(n) in the worst case. The recursion depth can be up to `n` for a skewed tree (e.g., a sorted array), which consumes O(n) space on the call stack.

Algorithms

Divide and Conquer

Data structures

Array Stack Monotonic Stack Tree Binary Tree

Prompt

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 <= 1000
0 <= nums[i] <= 1000
All integers in nums are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is a direct translation of the problem's definition into a recursive algorithm. It works by finding the maximum element in the current range of the array, making it the root of a subtree, and then recursively performing the same process for the left and right subarrays formed by splitting the array at the maximum element's position.

Algorithm

Define a recursive function build(nums, left, right) that constructs a tree from the subarray nums[left...right].
Base Case: If left > right, the subarray is empty, so return null.
Recursive Step:
1. Find the index maxIndex of the maximum element within nums[left...right] by linearly scanning the subarray.
2. Create a new TreeNode with the value nums[maxIndex]. This is the root of the current subtree.
3. The left child of this root is the result of a recursive call on the subarray to the left of the maximum element: build(nums, left, maxIndex - 1).
4. The right child of this root is the result of a recursive call on the subarray to the right of the maximum element: build(nums, maxIndex + 1, right).
5. Return the created root node.
The initial call to the function is build(nums, 0, nums.length - 1).

Walkthrough

The core of this method is a helper function that takes the array and two indices, left and right, defining the current subarray to be processed. In each call, the function scans this subarray to find the maximum value and its index. This maximum value becomes the value of the new root TreeNode. The function then calls itself recursively to build the left subtree from the part of the array to the left of the maximum element (left to maxIndex - 1) and the right subtree from the part to the right (maxIndex + 1 to right). The base case for the recursion is when the left index becomes greater than the right index, indicating an empty subarray, for which null is returned.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode constructMaximumBinaryTree(int[] nums) {18        if (nums == null || nums.length == 0) {19            return null;20        }21        return build(nums, 0, nums.length - 1);22    }23 24    private TreeNode build(int[] nums, int left, int right) {25        if (left > right) {26            return null;27        }28 29        // Find the index of the maximum element in the current range30        int maxIndex = left;31        for (int i = left + 1; i <= right; i++) {32            if (nums[i] > nums[maxIndex]) {33                maxIndex = i;34            }35        }36 37        // Create the root node with the maximum value38        TreeNode root = new TreeNode(nums[maxIndex]);39 40        // Recursively build the left and right subtrees41        root.left = build(nums, left, maxIndex - 1);42        root.right = build(nums, maxIndex + 1, right);43 44        return root;45    }46}

Complexity

Time

O(n^2) in the worst case. For each node created, we might scan a large portion of the array to find the next maximum. In the worst case (a sorted array), the work done is proportional to `n + (n-1) + ... + 1`, which is O(n^2). The average case is O(n log n).

Space

O(n) in the worst case. The recursion depth can be up to `n` for a skewed tree (e.g., a sorted array), which consumes O(n) space on the call stack.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem description.
It's a good starting point for solving the problem.

Cons

The repeated scanning for the maximum element in overlapping subarrays is inefficient.
Leads to a quadratic time complexity in the worst-case scenario (e.g., a sorted input array).

This is a highly efficient O(n) approach that constructs the tree in a single pass. It utilizes a monotonic stack (specifically, a stack that keeps node values in decreasing order) to maintain the right spine of the tree built so far. As each new element from the input array is processed, the stack is adjusted to correctly position the new node in the tree by wiring up the parent-child relationships.

Algorithm

Initialize an empty stack (a Deque is suitable) to store TreeNodes.
Iterate through each number num in the input array nums.
For each num, create a currentNode = new TreeNode(num).
While the stack is not empty and the value of the node at the top of the stack is less than num:
- The node at the top of the stack is smaller than currentNode. This means currentNode is the first larger element to its right. Therefore, the top node must be in the left subtree of currentNode.
- Pop the node from the stack and set it as the left child of currentNode. currentNode.left = stack.pop().
After the while loop, if the stack is not empty, the node now at the top is greater than currentNode. This means currentNode must be in its right subtree. Set stack.peek().right = currentNode.
Push currentNode onto the stack.
After iterating through all numbers, the root of the entire tree is the only element remaining at the bottom of the stack. Return stack.getFirst().

Walkthrough

The algorithm processes numbers from left to right. A stack is used to keep track of the nodes that form the 'right contour' or 'right spine' of the tree constructed so far. The values of nodes in the stack are always in decreasing order from bottom to top.

When we encounter a new number num, we create a currentNode for it. We then pop all nodes from the stack that have a value smaller than num. The last node popped (which is the largest among all popped nodes) becomes the left child of currentNode. This is because currentNode is the first element to their right that is larger than them. After this, if the stack is not empty, the node at the top of the stack has a value larger than num. This means currentNode must be the right child of that node. Finally, currentNode is pushed onto the stack to maintain the invariant.

After iterating through all the numbers, the node at the bottom of the stack is the root of the complete tree.

1import java.util.Deque;2import java.util.LinkedList;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    public TreeNode constructMaximumBinaryTree(int[] nums) {21        Deque<TreeNode> stack = new LinkedList<>();22        for (int num : nums) {23            TreeNode currentNode = new TreeNode(num);24            // Pop nodes from stack that are smaller than the current node.25            // The last popped node will become the left child of the current node.26            while (!stack.isEmpty() && stack.peekLast().val < num) {27                currentNode.left = stack.removeLast();28            }29            // If stack is not empty, the current node is the right child30            // of the node at the top of the stack.31            if (!stack.isEmpty()) {32                stack.peekLast().right = currentNode;33            }34            // Push the current node onto the stack.35            stack.addLast(currentNode);36        }37        // The root of the tree is the first element that was added to the stack.38        return stack.isEmpty() ? null : stack.getFirst();39    }40}

Complexity

Time

O(n). Each node corresponding to a number in `nums` is pushed onto the stack exactly once and popped from the stack at most once. All operations are amortized constant time, leading to a linear time overall.

Space

O(n). The auxiliary space is for the stack. In the worst-case scenario (e.g., a descending sorted array like `[5, 4, 3, 2, 1]`), the stack will hold all `n` nodes.

Trade-offs

Pros

Optimal time complexity of O(n).
Builds the tree in a single pass over the input array.
Efficient use of space.

Cons

The logic is more complex and less intuitive compared to the direct recursive approach.
Requires a solid understanding of monotonic stacks and their application.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int [] nums ; public TreeNode constructMaximumBinaryTree ( int [] nums ) { this . nums = nums ; return dfs ( 0 , nums . length - 1 ); } private TreeNode dfs ( int l , int r ) { if ( l > r ) { return null ; } int i = l ; for ( int j = l ; j <= r ; ++ j ) { if ( nums [ i ] < nums [ j ]) { i = j ; } } TreeNode root = new TreeNode ( nums [ i ]); root . left = dfs ( l , i - 1 ); root . right = dfs ( i + 1 , r ); return root ; } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * constructMaximumBinaryTree ( vector < int >& nums ) { return dfs ( nums , 0 , nums . size () - 1 ); } TreeNode * dfs ( vector < int >& nums , int l , int r ) { if ( l > r ) return nullptr ; int i = l ; for ( int j = l ; j <= r ; ++ j ) { if ( nums [ i ] < nums [ j ]) { i = j ; } } TreeNode * root = new TreeNode ( nums [ i ]); root -> left = dfs ( nums , l , i - 1 ); root -> right = dfs ( nums , i + 1 , r ); return root ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def constructMaximumBinaryTree ( self , nums : List [ int ]) -> Optional [ TreeNode ]: def dfs ( nums ): if not nums : return None val = max ( nums ) i = nums . index ( val ) root = TreeNode ( val ) root . left = dfs ( nums [: i ]) root . right = dfs ( nums [ i + 1 :]) return root return dfs ( nums )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem