Skip to main content
Talentd

Maximum Binary Tree II - Solution & Explanation

MediumTreeBinary Tree16 min readAsked at: Meta
Practice this problem

Problem Statement

A maximum tree is a tree where every node has a value greater than any other value in its subtree.

You are given the root of a maximum binary tree and an integer val.

Just as in the previous problem, the given tree was constructed from a list a (root = Construct(a)) recursively with the following Construct(a) routine:

  • If a is empty, return null.
  • Otherwise, let a[i] be the largest element of a. Create a root node with the value a[i].
  • The left child of root will be Construct([a[0], a[1], ..., a[i - 1]]).
  • The right child of root will be Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]).
  • Return root.

Note that we were not given a directly, only a root node root = Construct(a).

Suppose b is a copy of a with the value val appended to it. It is guaranteed that b has unique values.

Return Construct(b).

 

Example 1:

Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: a = [1,4,2,3], b = [1,4,2,3,5]

Example 2:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
Explanation: a = [2,1,5,4], b = [2,1,5,4,3]

Example 3:

Input: root = [5,2,3,null,1], val = 4
Output: [5,2,4,null,1,3]
Explanation: a = [2,1,5,3], b = [2,1,5,3,4]

 

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 <= val <= 100

Approach Overview

Problem Overview: You are given the root of a maximum binary tree built from an array and a new value val appended to that array. The task is to update the tree so it represents the maximum binary tree of the new array after the insertion.

A maximum binary tree has two rules: the root is the maximum value in the array, and the left and right subtrees are built recursively from the elements on each side of that maximum. When a new value is appended, it can only affect nodes along the rightmost path of the tree.

Approach 1: Recursive Tree Modification (O(n) time, O(h) space)

This method directly simulates how the tree would change if the new value were appended to the array. Compare val with the current node. If val is greater than the current root, the new value becomes the new root and the previous tree becomes its left child. Otherwise, the insertion must occur somewhere in the right subtree because the value was appended to the end of the array. Recursively process root.right until the correct position is found. The recursion depth equals the tree height h, giving O(n) worst-case time and O(h) space due to the call stack. This approach is clean and closely matches the recursive definition of a tree.

Approach 2: Iterative Approach using Stack (O(n) time, O(n) space)

The iterative solution leverages a monotonic structure similar to how the original maximum binary tree can be built. Traverse the right spine of the tree using a stack to track nodes. While the stack top has a value smaller than val, pop nodes because the new value must become their parent. The last popped node becomes the left child of the new node. If a larger node remains on the stack, attach the new node as its right child. This approach avoids recursion and works well when you want explicit control over traversal. Time complexity is O(n) since each node is pushed and popped at most once, and auxiliary space is O(n). The logic relies on properties of binary tree structure and a monotonic stack.

Recommended for interviews: The recursive modification approach is typically expected because it directly uses the definition of a maximum binary tree and quickly leads to a clean solution. Interviewers often look for the key observation that the insertion only affects the rightmost path. The iterative stack version demonstrates deeper understanding of tree construction patterns and monotonic stacks, which can stand out in more advanced interviews.

Approach 1: Recursive Tree Modification

This approach involves recursively inserting the new value into the correct position in the maximum binary tree. The main idea is to find the correct place in the tree for the new value by comparing it with the current node values as we traverse the tree from top to bottom.

If the new value is greater than the root node, the new value becomes the new root, and the entire existing tree becomes its left subtree. Otherwise, recursively consider this insertion as a problem for the root's right subtree, as all existing left-side nodes are already smaller than the current root.

We define a TreeNode class to represent each node in the tree. The insertIntoMaxTree function accepts the root of the tree and an integer val. If the root is null (empty tree) or the val is greater than the root's value, we make val the new root node with the current root as its left child. Otherwise, we recursively try to insert val into the right subtree.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(n) in the worst case due to the recursion stack.

Try this approach in the editor →

Approach 2: Iterative Approach using Stack

This approach attempts to solve the problem using an iterative method with the help of a stack to simulate the recursive behavior. As the new value is only appended to the right-most part of the implied array, we have to check from right to left in the tree structure to find the appropriate place for the new value to maintain the maximum tree property.

The main idea is to traverse the right nodes of the tree using a stack until we find the correct position for the new node.

This solution uses a loop instead of a recursive approach to insert the node. We iterate down the chain of right children until we find a spot where the new node should be inserted. This will involve attaching the new node's left subtree as the right child of the current node.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(1) since additional structures (e.g., a stack) are not used.

Try this approach in the editor →

Approach 3: Recursion

If val is the maximum number, then make val the new root node, and root the left subtree of the new root node.

If val is not the maximum number, since val is the last appended number, it must be on the right side of root. Therefore, we can insert val as a new node into the right subtree of root.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the tree.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Approach 4: Iteration

Search the right subtree, find the node where curr.val \gt val \gt curr.right.val, then create a new node node, point node.left to curr.right, and then point curr.right to node.

Finally, return root.

The time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Tree Modification

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(n) in the worst case due to the recursion stack.

Iterative Approach using Stack

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(1) since additional structures (e.g., a stack) are not used.

Recursion—
Iteration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Tree ModificationO(n)O(h)Best general solution. Clean logic and closely follows the definition of a maximum binary tree.
Iterative Stack ApproachO(n)O(n)Useful when avoiding recursion or when applying monotonic stack patterns.

Video Solution

998. Maximum Binary Tree II • Muerde un zombie • 364 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Binary Tree II easy or hard?
Maximum Binary Tree II is classified as a Medium problem. The main difficulty is recognizing that the new value only affects the rightmost path of the tree. Once that insight is clear, the recursive insertion logic becomes straightforward.
Maximum Binary Tree II Python/Java solution
Python and C++ solutions commonly use recursion to update the right subtree until the correct insertion point is found. Java and JavaScript implementations often demonstrate the iterative stack method to avoid recursion while preserving the maximum tree property.
How to solve Maximum Binary Tree II in O(n)?
Traverse only the right side of the tree since the inserted value corresponds to an element appended to the array. Compare the new value with nodes along the right path until a larger node is found or the end is reached. Insert the new node and reconnect children accordingly. Each node is visited at most once, giving O(n) time.
What is the best approach for Maximum Binary Tree II?
The recursive tree modification approach is the most common solution. Compare the new value with the current root and recurse only into the right subtree when the value is smaller. If the new value is larger, create a new root and attach the existing tree as its left child. This runs in O(n) worst-case time with O(h) recursion space.
Is Maximum Binary Tree II asked at Google/Amazon/Meta?
Tree modification and construction problems similar to Maximum Binary Tree II appear in interviews at companies like Amazon, Google, and Meta. Interviewers often use them to test understanding of tree properties, recursion, and structural transformations.
What data structure is used in Maximum Binary Tree II?
The core data structure is a binary tree. Some implementations also use a stack to manage nodes along the right spine and maintain a monotonic order while inserting the new value.
What is the time complexity of Maximum Binary Tree II?
Time complexity is O(n) in the worst case because the algorithm may traverse the entire right spine of the tree. In balanced trees the average complexity is closer to O(log n). Space complexity is O(h) for recursion, where h is the height of the tree.

Ready to solve this problem?

Practice Maximum Binary Tree II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Binary Tree