Maximum Binary Tree II

medium tree dfs recursion

Problem

A maximum tree is built from an array: the root is the maximum value, and its left and right children are the maximum trees of the elements before and after it. You are given the root of such a tree built from array a, and a value val that was appended to the end of a. Return the root of the maximum tree built from the new array. Equivalently, walk down the right spine: the first node whose value is smaller than val becomes the left child of a new node holding val; if no such node exists, val becomes the new right-most leaf.

Inputspine = [5, 4, 3, 2, 1], val = 6

Output6 is the new root; the old tree becomes its left child

Since val=6 is larger than the root 5, the entire old tree hangs to the left of the new root 6.

right spine values (comma-separated, decreasing)

val

def insertIntoMaxTree(root, val):
    if root is None or val > root.val:
        node = TreeNode(val)
        node.left = root
        return node
    root.right = insertIntoMaxTree(root.right, val)
    return root

function insertIntoMaxTree(root, val) {
  if (root === null || val > root.val) {
    const node = new TreeNode(val);
    node.left = root;
    return node;
  }
  root.right = insertIntoMaxTree(root.right, val);
  return root;
}

class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null || val > root.val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}

TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
    if (root == nullptr || val > root->val) {
        TreeNode* node = new TreeNode(val);
        node->left = root;
        return node;
    }
    root->right = insertIntoMaxTree(root->right, val);
    return root;
}

Explanation

The value val was appended to the end of the original array. In a maximum tree, anything that comes later in the array always lands somewhere along the tree's right spine — so we only ever need to walk right.

At each step there are two cases. If the current root is null, or val is larger than root.val, then val should sit above everything here: we make a new node for val, hang the existing subtree as its left child, and return it.

Otherwise val belongs further down, so we recurse into root.right and reattach whatever comes back. This keeps the rest of the tree untouched.

The node.left = root step works because everything already in the tree came earlier in the array, so it all sits to the left of the newly appended value.

Example: spine [5, 4, 3, 2, 1] with val = 6. Since 6 > 5 at the very root, the whole old tree becomes the left child of a brand new root 6.

Time: O(h) Space: O(h)