Maximum Binary Tree

medium tree array divide and conquer monotonic stack

Problem

Given an integer array with no duplicates, build the maximum binary tree: the root is the maximum element; the left subtree is built recursively from elements left of it; the right subtree from those right of it.

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

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

6 is the maximum; recurse on [3, 2, 1] (left) and [0, 5] (right).

nums (comma-separated)

def construct_maximum_binary_tree(nums):
    def build(lo, hi):
        if lo > hi:
            return None
        mi = lo
        for j in range(lo + 1, hi + 1):
            if nums[j] > nums[mi]:
                mi = j
        node = TreeNode(nums[mi])
        node.left  = build(lo, mi - 1)
        node.right = build(mi + 1, hi)
        return node
    return build(0, len(nums) - 1)

function constructMaximumBinaryTree(nums) {
  function build(lo, hi) {
    if (lo > hi) return null;
    let mi = lo;
    for (let j = lo + 1; j <= hi; j++) if (nums[j] > nums[mi]) mi = j;
    const node = { val: nums[mi], left: null, right: null };
    node.left  = build(lo, mi - 1);
    node.right = build(mi + 1, hi);
    return node;
  }
  return build(0, nums.length - 1);
}

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int lo, int hi) {
        if (lo > hi) return null;
        int mi = lo;
        for (int j = lo + 1; j <= hi; j++) if (nums[j] > nums[mi]) mi = j;
        TreeNode node = new TreeNode(nums[mi]);
        node.left  = build(nums, lo, mi - 1);
        node.right = build(nums, mi + 1, hi);
        return node;
    }
}

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        int mi = lo;
        for (int j = lo + 1; j <= hi; j++) if (nums[j] > nums[mi]) mi = j;
        TreeNode* node = new TreeNode(nums[mi]);
        node->left  = build(lo, mi - 1);
        node->right = build(mi + 1, hi);
        return node;
    };
    return build(0, (int) nums.size() - 1);
}

Explanation

The rule for building this tree is recursive by definition: the biggest value in a range becomes the root, and the elements to its left and right form the left and right subtrees. So we solve it with straightforward divide and conquer.

The helper build(lo, hi) works on the slice of nums from index lo to hi. If lo > hi the range is empty and we return null.

Otherwise we scan that range to find the index mi of the maximum value, make a node for nums[mi], then recurse: build(lo, mi - 1) for the left child and build(mi + 1, hi) for the right child.

Example: [3, 2, 1, 6, 0, 5]. The max is 6 at index 3, so it is the root. We then build the left subtree from [3, 2, 1] and the right subtree from [0, 5], repeating the same split on each piece.

In the worst case (a sorted array) finding the max each time costs O(n²), though a monotonic stack can bring this down to O(n).

Time: O(n²) worst, O(n) with monotonic stack Space: O(h) recursion stack