Maximum Binary Tree

Problem

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. 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

Source: Leetcode 654. Maximum Binary Tree

Solution

We can solve this problem by following the instructions in problem description. We can recursively find the largest element from input array, and then divide the array into two parts. For each part apply the same method of finding max value. In each step we will create a new node with the max value. Finally, when there is no way to split the array, the recursion will return null.

Below is the code for understanding.

/**
 * 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:
    
    int get_max_index(vector<int>& nums, int left, int right){
        int max_index = left;
        for(int i = left; i <= right; i++){
            if(nums[max_index] < nums[i]){
                max_index = i;
            }
        }
        return max_index;
    }
    
    TreeNode* rec(vector<int>& nums, int left, int right){
        if(left > right)
            return NULL;
        int max_index = get_max_index(nums, left, right);
        TreeNode* node = new TreeNode(nums[max_index]);
        node->left = rec(nums, left, max_index - 1);
        node->right = rec(nums, max_index + 1, right);
        return node;
    }
    
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int len = nums.size();
        return rec(nums, 0, len - 1);
    }
};

Conclusion

This is a straight forward recursion problem. If it is not properly understood, please write some comments. Happy coding 🙂