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.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    const construct = (start, end) => {
        if (start > end) {
            return null;
        }
        let max = -Infinity;
        let index = -1;
        for (let i = start; i <= end; i++) {
            if (max < nums[i]) {
                max = nums[i];
                index = i;
            }
        }
        const node = new TreeNode(max);
        node.left = construct(start, index - 1);
        node.right = construct(index + 1, end);
        return node;
    }
    return construct(0, nums.length - 1);
};

We will implement a DFS solution. We find the max value in nums[start:end + 1] as the current node value, and recursively create the left and right subtrees with updated start and end values.

Follow-up

Can you come up with an O(n) runtime solution?

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    const stack = [];
    for (const n of nums) {
        const node = new TreeNode(n);
        while (n > stack[stack.length - 1]?.val) {
            node.left = stack.pop();
        }

        if (stack.length) {
            stack[stack.length - 1].right = node;
        }
        stack.push(node);
    }
    return stack[0];
};

This solution is a little tricky to understand. Observe that at any point in time, the nodes in stack are both monotonically decreasing in terms of value, and are ordered by their index in nums. As we iterate through nums:

• If the current value nums[i] is less than our previous value stack[-1], then it must belong in the right subtree of stack[-1]. This is because, by definition, when we split at stack[-1], nums[i] will be split into the right subtree due to it being after stack[-1] in index.
• If the current value nums[i] is greater than our previous value stack[-1], we find all nodes in stack until stack is empty or the next node in stack has a greater value than nums[i]. All the values up to that point are in the left subtree of nums[i]. This is because, by definition, when we split at nums[i], those values to the left of nums[i] which are less than nums[i] and consecutive will be split into the left subtree due to them being before nums[i] in index.
  • If stack is not empty at this point, then there must exist a node in stack with greater value than nums[i]. Then nums[i] must belong in the right subtree of stack[-1] (same explanation as first bullet point).

Finally, we push nums[i] into stack and repeat this process. The root of the constructed tree is stack[0], since it is the node with the largest value in the entire tree.

This solution has runtime O(n) since each node is pushed into stack exactly once (and so there can only be n pops at most in total as we iterate through nums).