654. Maximum Binary Tree

MediumStackTreeArrayDivide and ConquerBinary TreeMonotonic Stack

Problem Description

You are given an array named nums, which contains a set of integers and has no duplicate elements. Your task is to use this array to build what's called a maximum binary tree. This tree is constructed using a specific set of rules:

The maximum value in the array becomes the root node of the tree.
The subarray to the left of the maximum value is used to construct the left subtree of the tree by applying the same rule.
Similarly, the subarray to the right of the maximum value is used to build the right subtree by applying the same rule.

This process is recursive, meaning that you apply the same set of rules to each subarray (left and right of the maximum value found) to build the entire tree. The goal is to construct and return the maximum binary tree.

Intuition

To build the maximum binary tree, we need to find the maximum element in the array and make it the root of the tree. We then split the array into two subarrays: one to the left and one to the right of where the maximum value was found. These subarrays will be used to construct the left and right subtrees, respectively. We follow the same strategy recursively for the subtrees.

This approach leads us to divide-and-conquer strategy, where we divide the problem into smaller instances of the same problem (finding the maximum element and building left and right subtrees) and then combine the solutions (subtrees) to construct the final tree.

The provided solution uses a helper function dfs that implements this recursive strategy. The base case for the recursion is when there are no elements in the current subarray (nums), in which case the function returns None because there's nothing left to construct.

When elements are present, the function:

Finds the maximum value in the current subarray.
Determines the index of this maximum value.
Creates a new tree node with the maximum value.
Recursively calls itself to build the left subtree with the elements to the left of the maximum value.
Recursively calls itself to build the right subtree with the elements to the right of the maximum value.
Links the constructed left and right subtrees to the created node (now the parent node).
Returns the current tree node (which forms a part of the larger tree).

The recursion unwinds, building up the entire tree, which is finally returned by the outermost call to dfs.

Learn more about Stack, Tree, Divide and Conquer, Binary Tree and Monotonic Stack patterns.

Solution Approach

The solution implementation makes use of the divide-and-conquer strategy, recursion, and the binary tree data structure. Here's how these concepts are applied to construct the maximum binary tree:

Divide and Conquer: The array nums is repeatedly divided into two subarrays around the maximum value found. This approach splits the problem into smaller problems, specifically building the left and right subtrees.
Recursion: To manage the repetitive task of building subtrees from subarrays, the solution implements a recursive helper function dfs(). Recursion continues until the base case is met, which occurs when the passed-in subarray is empty (not nums), at which point the function returns None since there are no more nodes to create.
Binary Tree Construction: The nature of the problem requires constructing a binary tree, so the TreeNode class is used to create tree nodes. Each node has a value as well as potential left and right children, which correspond to the left and right subtrees.

When employing recursion to build the tree, the approach is as follows:

a. Identify the maximum value val in the current subarray nums using the max() function and find its index i with nums.index(val).

b. Create a new TreeNode with val as its value, which will serve as the root node for the current (sub)tree.

c. For the left child of the current node, recursively call dfs(nums[:i]), which constructs the subtree from the elements to the left of val.

d. For the right child, a similar recursive call is made with dfs(nums[i + 1:]) to build the subtree from the elements to the right of val.

e. After the recursive calls, the left and right children are connected to the root node of the subtree, thereby completing the subtree construction.

Each recursive call builds a part of the tree and returns it to the calling function, which then attaches it to the appropriate left or right child of the current node. This step-by-step process continues until the original call returns the entire maximum binary tree, which is the final output of the constructMaximumBinaryTree function.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Let's say we have the following array nums:

nums = [3, 2, 1, 6, 0, 5]

According to the problem description, we need to construct a maximum binary tree following the given rules. Here's how the approach solves this:

Find the maximum value in nums. In this case, it is 6.
Since 6 is the maximum value, it will be the root of the maximum binary tree.
Divide the array into two subarrays around the maximum value found. Here we have left_sub = [3, 2, 1] and right_sub = [0, 5].
To construct the left subtree, repeat the same process for left_sub. Find the maximum value, which is 3, and make it the left child of 6.
The subarray to the left of 3 is empty, so the left child of 3 would be None. The subarray to the right of 3 is [2, 1].
- Find the maximum value in [2, 1], which is 2, and make it the right child of 3.
- Now, 2 will have a right child which is 1, as 2 is the maximum and only element in the subarray to its left, and no elements are to its right.
For the right subtree of the root 6, we examine right_sub. The maximum value in [0, 5] is 5, so 5 becomes the right child of 6.
Repeat the process for the subarray to the left of 5, which is [0]. Since 0 is the only element, it becomes the left child of 5. No elements are to the right of 5, so its right child is None.

The final maximum binary tree constructed from nums looks like this:

This example demonstrates the divide-and-conquer and recursive nature of the solution, where the maximum value in each subarray becomes the root of a subtree, with recursive calls constructing its children until the entire tree is built.

Solution Implementation

1from typing import List, Optional
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
12        # Helper function to construct the tree using a divide and conquer approach
13        def build_max_tree(sub_nums):
14            # Base case: if there are no numbers, return None
15            if not sub_nums:
16                return None
17          
18            # Find the maximum value in the list of numbers
19            max_value = max(sub_nums)
20            # Find the index of the maximum value
21            max_index = sub_nums.index(max_value)
22          
23            # Create a tree node with the maximum value
24            root = TreeNode(max_value)
25            # Recursively build the left subtree using the elements to the left of the max value
26            root.left = build_max_tree(sub_nums[:max_index])
27            # Recursively build the right subtree using the elements to the right of the max value
28            root.right = build_max_tree(sub_nums[max_index + 1:])
29          
30            return root
31
32        # Call the helper function with the initial list of numbers
33        return build_max_tree(nums)
34
35# This constructs a maximum binary tree as defined by the problem statement,
36# where the root is the maximum number in the array, and the left and right subtrees
37# are constructed from the elements before and after the maximum number, respectively.
38

1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6    TreeNode() {}
7    TreeNode(int val) { this.val = val; }
8    TreeNode(int val, TreeNode left, TreeNode right) {
9        this.val = val;
10        this.left = left;
11        this.right = right;
12    }
13}
14
15class Solution {
16    // Declare an array to hold the input values
17    private int[] nodeValues;
18
19    /**
20     * This method constructs a maximum binary tree from the given array.
21     * 
22     * @param nums The input array containing elements to be used in the tree.
23     * @return The constructed maximum binary tree's root node.
24     */
25    public TreeNode constructMaximumBinaryTree(int[] nums) {
26        this.nodeValues = nums;
27        // Start the recursive tree construction process from the full range (0 to length-1)
28        return constructTreeInRange(0, nums.length - 1);
29    }
30
31    /**
32     * This private helper method creates the maximum binary tree recursively.
33     * 
34     * @param left The left boundary (inclusive) of the current subarray.
35     * @param right The right boundary (inclusive) of the current subarray.
36     * @return The root node of the constructed subtree.
37     */
38    private TreeNode constructTreeInRange(int left, int right) {
39        // Base case: when the left index is greater than the right, we've gone past the leaf node
40        if (left > right) {
41            return null;
42        }
43      
44        int maxIndex = left; // Start with the leftmost index
45      
46        // Find the index of the maximum element in the current subarray
47        for (int j = left; j <= right; ++j) {
48            if (nodeValues[maxIndex] < nodeValues[j]) {
49                maxIndex = j;
50            }
51        }
52      
53        // Create a new tree node with the maximum element as its value
54        TreeNode root = new TreeNode(nodeValues[maxIndex]);
55      
56        // Recursively construct the left subtree using elements left to the maximum element
57        root.left = constructTreeInRange(left, maxIndex - 1);
58      
59        // Recursively construct the right subtree using elements right to the maximum element
60        root.right = constructTreeInRange(maxIndex + 1, right);
61      
62        return root; // Return the root node of the constructed subtree
63    }
64}
65

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val; // The value of the node
6    TreeNode *left; // Pointer to the left child
7    TreeNode *right; // Pointer to the right child
8
9    // Constructor for a tree node with a given value, initially with no children
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11
12    // Constructor for a tree node with given value, left and right children
13    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16class Solution {
17public:
18    /**
19     * Constructs a maximum binary tree from the given integer array.
20     * @param nums The vector of integers.
21     * @return The root TreeNode of the constructed maximum binary tree.
22     */
23    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
24        return constructTree(nums, 0, nums.size() - 1);
25    }
26
27private:
28    /**
29     * Helper function to construct the maximum binary tree using Depth First Search.
30     * @param nums The vector of integers.
31     * @param left The left boundary of the current segment.
32     * @param right The right boundary of the current segment.
33     * @return The root TreeNode of the constructed maximum binary tree for the segment.
34     */
35    TreeNode* constructTree(vector<int>& nums, int left, int right) {
36        // If the current segment is invalid, return nullptr to indicate no subtree
37        if (left > right) return nullptr;
38
39        // Find the index of the maximum element in the current segment
40        int maxIndex = left;
41        for (int currentIndex = left; currentIndex <= right; ++currentIndex) {
42            if (nums[maxIndex] < nums[currentIndex]) {
43                maxIndex = currentIndex;
44            }
45        }
46
47        // Create the root node of the subtree with the maximum element
48        TreeNode* root = new TreeNode(nums[maxIndex]);
49
50        // Recursively construct the left subtree with the elements before the maximum element
51        root->left = constructTree(nums, left, maxIndex - 1);
52
53        // Recursively construct the right subtree with the elements after the maximum element
54        root->right = constructTree(nums, maxIndex + 1, right);
55
56        // Return the root of the subtree
57        return root;
58    }
59};
60

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    // Constructor to create a tree node with given values, default to 0 for val and null for left and right.
8    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
9        this.val = val;
10        this.left = left;
11        this.right = right;
12    }
13}
14
15// Function to construct a maximum binary tree from an array of numbers.
16// A maximum binary tree is a binary tree where every node has a value greater than its children.
17function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
18    // If the array is empty, return null as no tree can be constructed.
19    if (nums.length === 0) {
20        return null;
21    }
22
23    // Find the maximum value and its index in the array.
24    // The reduce method processes each number, keeping track of the largest number and its index.
25    let maxValueIndex = nums.reduce<[number, number]>((currentMax, value, index) => {
26        return (currentMax[0] < value) ? [value, index] : currentMax;
27    }, [-Infinity, -1]);
28  
29    // Destructure the result to get max value and index.
30    const [maxValue, maxIndex] = maxValueIndex;
31
32    // Recursively build the tree:
33    // - The maximum value becomes the root.
34    // - The left child is constructed from the subarray left of the maximum value.
35    // - The right child is constructed from the subarray right of the maximum value.
36    let rootNode = new TreeNode(
37        maxValue,
38        constructMaximumBinaryTree(nums.slice(0, maxIndex)),
39        constructMaximumBinaryTree(nums.slice(maxIndex + 1))
40    );
41
42    // Return the constructed tree node.
43    return rootNode;
44}
45

Time and Space Complexity

Time Complexity

The time complexity of the function constructMaximumBinaryTree is determined by multiple factors: the number of elements in the nums list, finding the maximum value in the current portion of the list, splitting the list into two parts, and recursively building the left and right subtrees.

For each node of the binary tree, finding the maximum element takes O(n) time where n is the number of elements in the current portion of the list.
The nums.index(val) operation also takes O(n) time for each node to find the index of the maximum element.
The dfs function is called recursively for each element in the list to create a node, meaning there will be n calls in total (where n is the size of the original list).

Considering the recursive nature and that finding the max and index takes linear time at each level of recursion, the total time complexity is O(n^2) in the worst case, when the input list is sorted in ascending or descending order, causing the divide step to only reduce the problem size by 1 each time.

Space Complexity

The space complexity is determined by the recursive stack depth and the space needed to store the constructed binary tree.

In the best case (when the input list is already balanced), the depth of the recursive stack is O(log n) since the tree would be roughly balanced. This would happen when the maximum element always ends up being in the middle of the current subarray.
In the worst case (input list is sorted), the depth of the recursive stack is O(n) because the constructed tree would be skewed (like a linked list), and hence we would have a chain of recursive calls equal to the size of the input list.

Because the space needed to store the binary tree is O(n) and the recursive stack space in the worst case is also O(n), the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know