How to Construct the Maximum Binary Tree using Divide-and-Conquer Recursion Algorithm?

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

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

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Note:
The size of the given array will be in the range [1,1000].

Constructing the Maximum Binary Tree using Depth First Search Algorithm (Divide and Conquer)

Do what it says: find the maximum number first, then divide the array into two halves which correspond to the left and right subtree respectively. We define a helper function which takes the vector and the two index pointers that define the current range of the vector being looked at.

Recursively, we can use the Depth First Search (DFS) algorithm to construct the left and right sub tree respectively. The complexity is O(N^2) where N is the number of the elements in the array: On the first round, it takes O(N) to find the maximum element index, and the left and right tree take another N (N/2+N/2) to find the maximum element index. This continues: N + (N/2 + N/2) + (N/4 + N/4 + N/4 + N/4) … + 1 which sums up to O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int maxIndex = left;
        int maxValue = nums[maxIndex];
        // find the maximum value index in the range of [left, right]
        for (int i = left + 1; i <= right; ++ i) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        auto root = new TreeNode(maxValue);
        root->left = helper(nums, left, maxIndex - 1);
        root->right = helper(nums, maxIndex + 1, right);
        return root;
    }
    
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root = helper(nums, 0, nums.size() - 1);
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int maxIndex = left;
        int maxValue = nums[maxIndex];
        // find the maximum value index in the range of [left, right]
        for (int i = left + 1; i <= right; ++ i) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        auto root = new TreeNode(maxValue);
        root->left = helper(nums, left, maxIndex - 1);
        root->right = helper(nums, maxIndex + 1, right);
        return root;
    }
    
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root = helper(nums, 0, nums.size() - 1);
        return root;
    }
};

We can implement the DFS without a helper function: we can use std::max_element to find the iterator that has the maximum value, then we can recursively construct the left and right sub tree if applicable e.g. if the max iterator is not either begin or the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty()) return NULL;
        auto m = max_element(begin(nums), end(nums));
        TreeNode* root = new TreeNode(*m);
        if (m != begin(nums)) {
            vector<int> left(begin(nums), m);
            root->left = constructMaximumBinaryTree(left);
        }
        if (m != end(nums) - 1) {
            vector<int> right(m + 1, end(nums));
            root->right = constructMaximumBinaryTree(right);
        }
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty()) return NULL;
        auto m = max_element(begin(nums), end(nums));
        TreeNode* root = new TreeNode(*m);
        if (m != begin(nums)) {
            vector<int> left(begin(nums), m);
            root->left = constructMaximumBinaryTree(left);
        }
        if (m != end(nums) - 1) {
            vector<int> right(m + 1, end(nums));
            root->right = constructMaximumBinaryTree(right);
        }
        return root;
    }
};

The std::end() iterator is actually one element beyond the last element.

Related Binary Tree Construction Algorithms

You may also like the following posts on the similar tree problems.

• Recursive Algorithm to Construct Binary Tree from Preorder and Postorder Traversal
• How to Construct Binary Search Tree from Preorder Traversal in Python?
• Algorithm to Construct Binary Tree from Preorder and Inorder Traversal
• How to Construct Binary Search Tree from Preorder Traversal? (C++ and Java)
• How to Construct String from Binary Tree?
• How to Balance a Binary Search Tree using Recursive Inorder Traversal Algorithm?
• How to Construct the Maximum Binary Tree using Divide-and-Conquer Recursion Algorithm?
• How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?
• How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —