We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Binary Tree II

Number: 1040

Difficulty: Medium

Paid? No

Companies: Meta

Problem Description

Given the root of a maximum binary tree—which is built recursively by choosing the maximum element as the root and partitioning the array into left and right subtrees—and an integer val, a new value is appended to the original array used to construct the tree. The task is to insert val into the tree such that the resulting tree remains a maximum binary tree constructed from the new array.

Key Insights

  • A maximum binary tree is constructed so that every node is greater than all nodes in its subtrees.
  • When appending a new value, if val is larger than the root, the new node becomes the new root with the original tree as its left child.
  • Otherwise, traverse the right subtree until finding a node such that the next right node is either null or less than val.
  • The new node’s left child then becomes the subtree that was previously the right child of the located node.
  • This greedy insertion along the right boundary ensures the tree properties are maintained.

Space and Time Complexity

Time Complexity: O(n) in the worst-case (skewed tree) where n is the number of nodes in the tree. Space Complexity: O(1) iterative solution (ignoring recursion stack space if recursion is used).

Solution

We can solve the problem efficiently by iteratively walking the right boundary of the given tree. If the inserted value val is greater than the root’s value, then simply create a new node with val and assign the old tree as its left child. Otherwise, starting from the root, iterate along the right children. When you find a node whose right child is either null or has a smaller value than val, create a new node with val. Set the new node's left pointer to that node's right child, and then update the node's right pointer to point to the new node. This procedure preserves the maximum binary tree properties.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def insertIntoMaxTree(root, val):
    # If tree is empty or new value is greater than the root value,
    # create a new node and put the current tree as its left child.
    if not root or val > root.val:
        new_node = TreeNode(val)
        new_node.left = root
        return new_node

    # Set current pointer to traverse the tree
    curr = root
    # While there is a right child, and it is greater than new value,
    # move the pointer to the right.
    while curr.right and curr.right.val > val:
        curr = curr.right

    # At this position, the new node should be inserted.
    new_node = TreeNode(val)
    # New node's left child becomes what was the right child.
    new_node.left = curr.right
    # Attach the new node as the right child.
    curr.right = new_node
    return root
← Back to All Questions