Maximum Binary Tree II: Rightmost Path Insertion

You are given a maximum binary tree that was built from some array a, and you are given a value val. Your task is to return the tree that would result from appending val to the end of a and then rebuilding the maximum binary tree. This is LeetCode 998: Maximum Binary Tree II, and the good news is that you do not need to rebuild the entire tree from scratch. Because val is appended to the end of the array, only the rightmost path of the tree can change.

Why this problem matters

Maximum Binary Tree II builds directly on the construction logic from Maximum Binary Tree (LeetCode 654). That problem teaches you how a maximum binary tree is defined: the root is the maximum element, and the left and right subtrees are recursively built from elements to the left and right of that maximum. This follow-up teaches you something deeper: how the structure of the tree relates to the order of elements in the underlying array.

Understanding the rightmost path property is the key. In a maximum binary tree, every node on the rightmost path corresponds to the maximum of a suffix of the original array. When you append a new element, you only disturb this suffix structure. Recognizing that saves you from an O(n) rebuild and gives you an elegant O(h) insertion, where h is the height of the rightmost path.

The key insight

Since val is appended to the end of the array, it only affects the rightmost path of the tree. Think about it this way: every node on the right spine represents the maximum of some subarray that extends to the end of a. When you add val at the end, you walk down the right spine comparing val to each node.

If val is larger than a node, that means val is now the maximum of that subarray. So val takes that node's position, and the entire subtree rooted at that node becomes val's left child (because those elements all appeared before val in the array).

If val is smaller than everything on the right spine, it simply becomes the rightmost leaf of the tree.

There is one special case: if val is larger than the root itself, then val becomes the new root and the entire old tree becomes its left child.

The solution

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

    root.right = insertIntoMaxTree(root.right, val)
    return root

The recursive version is clean and short. If the current node is None or val is greater than the current node's value, you create a new node with val and attach the current subtree as its left child. Otherwise, you recurse into the right subtree, because val must be inserted somewhere further down the right spine.

The iterative version walks the right spine explicitly, but the recursive approach captures the logic more clearly. Each recursive call moves one step down the rightmost path, and the base case handles both insertion points: when val is bigger than the current node, or when you have fallen off the bottom of the tree.

Visual walkthrough

Let's trace through inserting val=3 into the maximum binary tree built from [5, 2, 4, 1]. The original tree has right spine: 5, 4, 1.

The walk was short: only three comparisons along the right spine. Node 3 found its place between 4 and 1 in the decreasing sequence. The old subtree rooted at 1 became 3's left child, preserving the maximum binary tree property for the extended array [5, 2, 4, 1, 3].

Complexity analysis

Time is O(n) in the worst case, where n is the number of nodes. This happens when the right spine contains every node (the tree is a left-skewed chain, meaning the original array was sorted in ascending order). In the average case, the right spine has O(log n) nodes, giving O(log n) time.

Space is O(n) for the recursion stack in the worst case, matching the depth of the right spine. You can reduce this to O(1) space by using an iterative approach with a parent pointer, but the recursive version is easier to reason about.

Note that this is much better than rebuilding the tree from scratch, which would require O(n) time and O(n) space regardless of the tree's shape.

The building blocks

1. Maximum binary tree property

A maximum binary tree has the property that every node is the maximum of its subtree's corresponding subarray. The root is the global maximum. The left child is the maximum of elements before the root in the array, and the right child is the maximum of elements after it. This recursive definition is what makes the rightmost path special: it encodes the suffix maximums.

2. Rightmost path traversal

Walking the right spine of a tree is a pattern that appears in several problems. You follow node.right at each step, processing nodes in order from root to the deepest right descendant. In this problem, you are looking for the insertion point where val first exceeds a node's value. In problems like Binary Tree Right Side View, you use the rightmost path to find visible nodes. The traversal is the same, only the decision logic changes.

Edge cases

• val larger than root: val becomes the new root, and the entire old tree becomes its left child. The recursive solution handles this naturally with the val > root.val check.
• val smaller than everything: val becomes the rightmost leaf. The recursion walks all the way down the right spine until root is None, then creates the new node there.
• Single node tree: If the tree has one node with value x and val > x, the new node becomes the root with x as its left child. If val is smaller than or equal to x, the new node becomes the right child.
• Already right-skewed tree: The insertion walks the entire right spine, which is the worst case for time and space.

From understanding to recall

You have seen how the insertion works: walk the right spine, find where val fits in the decreasing sequence, splice it in. The code is four lines of recursion. But writing those four lines correctly under pressure requires knowing exactly when to create the new node, which child to set, and how to handle the None case.

The details that trip people up: remembering that the displaced subtree becomes the left child (not the right child), remembering that the base case includes both not root and val > root.val, and remembering to recurse on root.right specifically (not root.left). These are small distinctions, but getting any of them wrong produces an invalid tree.

Spaced repetition locks in these details. You write the solution from scratch at increasing intervals until the pattern is automatic. After a few reps, you will not second-guess whether the old subtree goes left or right. You will just know.

Related posts

• Maximum Binary Tree - The original construction problem that defines the maximum binary tree structure
• Insert into a Binary Search Tree - Another tree insertion pattern where you walk a specific path to find the right position
• Binary Tree Right Side View - Uses rightmost path traversal to identify visible nodes from the right side

The rightmost path property is the core of this problem. Once you see that appending to the array only affects the right spine, the solution writes itself. CodeBricks breaks this insight into its building blocks and drills them with spaced repetition, so the next time you see a tree modification problem, you already know where to look.