Maximum Binary Tree II

Medium
1937.

Maximum Binary Tree II

Maximum Binary Tree II is a medium coding problem on binary search and trees, asked in Amazon interviews.

A maximum tree is built from an array a of distinct values: its root holds the maximum of a, the left subtree is the maximum tree of the elements before that maximum, and the right subtree the maximum tree of the elements after it (an empty part gives an empty subtree).

You are given the root of the maximum tree of some array a — but not a itself — and an integer value that does not occur in a. Let b be a with value appended at the end. Return the root of the maximum tree of b.

Example 1

Input
root = [4,1,3,null,null,2], value = 5
Output
[5,4,null,1,3,null,null,2]
Explanation
The tree was built from [1,4,2,3]; the new array [1,4,2,3,5] has 5 as its maximum, at the very end, so 5 becomes the root with the old tree as its left subtree.

Example 2

Input
root = [5,2,4,null,1], value = 3
Output
[5,2,4,null,1,null,3]
Explanation
Built from [2,1,5,4]; appending 3 gives [2,1,5,4,3], where 3 ends up as the right child of 4.

Example 3

Input
root = [5,2,3,null,1], value = 4
Output
[5,2,4,null,1,3]
Explanation
Built from [2,1,5,3]; in [2,1,5,3,4] the 4 sits right of 5 and takes 3 as its left child.

Constraints

  • The number of nodes in the tree is in the range [1, 100]
  • 1 <= Node.val <= 100
  • All the values of the tree are unique
  • 1 <= value <= 100
  • value does not occur in the tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} value
 * @return {TreeNode}
 */
var insertIntoMaxTree = function(root, value) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Binary Tree II — Solution in Python, Java & C++

Maximum Binary Tree II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.

Maximum Binary Tree II is a medium coding problem on binary search and trees, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Binary Search, Trees
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A maximum tree is built from an array a of distinct values: its root holds the maximum of a, the left subtree is the maximum tree of the elements before that maximum, and the right subtree the maximum tree of the elements after it (an empty part gives an empty subtree).

You are given the root of the maximum tree of some array a — but not a itself — and an integer value that does not occur in a. Let b be a with value appended at the end. Return the root of the maximum tree of b.

Example 1

Input: root = [4,1,3,null,null,2], value = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: The tree was built from [1,4,2,3]; the new array [1,4,2,3,5] has 5 as its maximum, at the very end, so 5 becomes the root with the old tree as its left subtree.

Example 2

Input: root = [5,2,4,null,1], value = 3
Output: [5,2,4,null,1,null,3]
Explanation: Built from [2,1,5,4]; appending 3 gives [2,1,5,4,3], where 3 ends up as the right child of 4.

Example 3

Input: root = [5,2,3,null,1], value = 4
Output: [5,2,4,null,1,3]
Explanation: Built from [2,1,5,3]; in [2,1,5,3,4] the 4 sits right of 5 and takes 3 as its left child.

Constraints

  • The number of nodes in the tree is in the range [1, 100]
  • 1 <= Node.val <= 100
  • All the values of the tree are unique
  • 1 <= value <= 100
  • value does not occur in the tree

Hints for Maximum Binary Tree II

  1. Hint 1

    The new element is the last one of b. Where does the last element of an array end up in its maximum tree?

  2. Hint 2

    If value is larger than the root, it is the new maximum and everything before it is its left part: a new root with the old tree on the left.

  3. Hint 3

    Otherwise the root stays, and value belongs to the part after the root's position — that part is the root's right subtree. Recurse to the right.

How to solve Maximum Binary Tree II

Appending at the end only touches the right spine of the tree, which holds the suffix maxima of a. Walk down that spine until a node smaller than value (or the end) is reached; value takes that position and adopts the rest of the spine as its left subtree.

Approach

  1. If root is null or root.val < value, return a new node holding value whose left child is root.
  2. Otherwise set root.right = insertIntoMaxTree(root.right, value) and return root.

Why it works

The root's position in b is unchanged when root.val > value, and value falls in the part after it, which is exactly the root's right subtree built from that suffix plus value — the same problem, smaller. When value exceeds the current subtree's maximum, it is the maximum of that range in b; since it is the last element, everything else in the range lies to its left, which is precisely the old subtree.

Complexity

  • Time — O(h) — one walk down the right spine
  • Space — O(h) for the recursion (O(1) iteratively)

Pitfalls

  • Only the right spine can change: never descend into a left subtree.
  • When value is the overall maximum, the entire old tree becomes its left subtree.
  • Rebuilding the whole tree from the in-order array also works but costs O(n^2).

Reference solution

Python

from typing import Optional

def insertIntoMaxTree(root: Optional[TreeNode], value: int) -> Optional[TreeNode]:
    if root is None or root.val < value:
        return TreeNode(value, root, None)
    root.right = insertIntoMaxTree(root.right, value)
    return root

Java

public static TreeNode insertIntoMaxTree(TreeNode root, int value) {
    if (root == null || root.val < value) return new TreeNode(value, root, null);
    root.right = insertIntoMaxTree(root.right, value);
    return root;
}

C++

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

JavaScript

var insertIntoMaxTree = function(root, value) {
    if (root === null || root.val < value) return new TreeNode(value, root, null);
    root.right = insertIntoMaxTree(root.right, value);
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 189 binary search problems · the whole catalogue

Learn the technique: Binary Search · Binary Trees and Tree Traversals