Problem

Given an array of integers with no duplicate values, we have to form a maximum binary tree. The maximum binary tree is constructed based on few rules:

• The root is the maximum number in the array.
• The left subtree is the maximum tree constructed from the left part subarray divided by the maximum number.
• The right subtree is the maximum tree constructed from the right part subarray divided by the maximum number.

We have to construct the maximum binary tree using the given array and output the root node.

Example

If we have the following array:

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

We will construct the maximum tree like this:

1
2
3      6
4    /   \
5   3     5
6    \    /
7     2  0
8       \
9        1

The maximum value is 6. Everything left of 6 forms the left subtree and everything right of 6 forms the right subtree. This process is repeated for the sub-arrays to find the left child and the right child for each node.

Solution

To solve this problem, we need to perform a depth-first search (DFS) on the array. For each function call, it will define a segment [i, j] along with its maximum element that will be the root of the subtree. The two segments that are divided by the maximum element number will recursively build the left subtree and the right subtree, respectively.

The max_element function is used to find the iterator pointing to the maximum element inside the range [i, j]. Then, we calculate the maximum value itself and the index of this maximum value. After that, we create the root node with the maximum number. Then, we build the left subtree and the right subtree by calling the build function recursively. The build function defines two subarrays, one to the left of the maximum element and the other to the right. The left subarray ranges from i to maxIndex - 1 and the right subarray ranges from maxIndex + 1 to j.

This algorithm works because the largest element in the array will be the root of the binary tree, and the largest element in the subarray to the left of the root will be the root's left child. Similarly, the largest element in the subarray to the right of the root will be the root's right child. This process continues recursively for each subarray and builds the entire binary tree.

C++

Class Definition

1
2cpp
3class TreeNode {
4public:
5  int val;
6  TreeNode* left;
7  TreeNode* right;
8  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13  TreeNode* constructMaximumBinaryTree(vector<int>& nums);
14private:
15  TreeNode* build(const vector<int>& nums, int i, int j);
16};

Method Definitions

1
2cpp
3TreeNode* Solution::constructMaximumBinaryTree(vector<int>& nums) {
4  return build(nums, 0, nums.size() - 1);
5}
6
7TreeNode* Solution::build(const vector<int>& nums, int i, int j) {
8  //Base condition
9  if (i > j)
10    return nullptr;
11
12  //Find the maximum element in the range [i,j]
13  const auto it = max_element(begin(nums) + i, begin(nums) + j + 1);
14  const int maxNum = *it;
15  const int maxIndex = it - begin(nums);
16  
17  //Create the root with maxNum
18  TreeNode* root = new TreeNode(maxNum);
19  
20  // Using recursion to construct the left and right subtree
21  root->left = build(nums, i, maxIndex - 1);
22  root->right = build(nums, maxIndex + 1, j);
23  
24  return root;
25}

Python

1
2python
3from typing import List 
4
5# Class Definition
6class TreeNode:
7    def __init__(self, x):
8        self.val = x
9        self.left = None
10        self.right = None
11
12class Solution:
13    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
14        if not nums:
15            return None
16            
17        max_val = max(nums)
18        max_index = nums.index(max_val)
19        
20        node = TreeNode(max_val)
21        node.left = self.constructMaximumBinaryTree(nums[:max_index])
22        node.right = self.constructMaximumBinaryTree(nums[max_index + 1:])
23        
24        return node

In Python, we follow a similar approach but use the built-in functions max and index to find the maximum value and its index in the list. The slicing operation is used to build the left and right subtree.

JavaScript

1
2javascript
3// Class Definition
4class TreeNode {
5    constructor(val, left = null, right = null) {
6        this.val = val;
7        this.left = left;
8        this.right = right;
9    }
10}
11
12const constructMaximumBinaryTree = nums => {
13    if (!nums.length) return null;
14    
15    let maxVal = Math.max(...nums);
16    let maxIndex = nums.indexOf(maxVal);
17    
18    let node = new TreeNode(maxVal);
19    node.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
20    node.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
21    
22    return node;
23};

In JavaScript, we use the spread operator (...) combined with the Math.max function to find the maximum value in the array. The indexOf method is used to find the index of this max value. The slice method is used to form the left and right subtree recursively.

Java

1
2java
3// Class Definition 
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8    TreeNode(int x) { val = x; }
9}
10
11class Solution {
12    public TreeNode constructMaximumBinaryTree(int[] nums) {
13        return build(nums, 0, nums.length - 1);
14    }
15    
16    private TreeNode build(int[] nums, int i, int j) {
17        if (i > j) 
18            return null;
19        
20        int maxIndex = i; 
21        for (int k = i; k <= j; k++) 
22            if (nums[k] > nums[maxIndex]) 
23                maxIndex = k;
24                
25        TreeNode node = new TreeNode(nums[maxIndex]);
26        node.left = build(nums, i, maxIndex - 1);
27        node.right = build(nums, maxIndex + 1, j);
28        
29        return node;
30    }
31}

In Java, we use a loop to find the maximum value and its index in the subarray. Like in C++, the build function is used recursively to form the left and right subtree.