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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Binary Tree II

Difficulty: Medium

Problem Description

Given the root of a maximum binary tree and an integer val, return the maximum binary tree constructed by adding val to the tree.

Key Insights

  • A maximum binary tree is defined such that each node is greater than any node in its subtree.
  • The construction of the tree is based on the largest element in the list, with the left and right children formed from the remaining elements.
  • To insert a new value, we must determine where it fits in the existing structure while maintaining the properties of the maximum binary tree.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since we may need to traverse the entire tree to find the correct position for the new value.

Space Complexity: O(h), where h is the height of the tree, due to the recursive call stack.

Solution

To solve the problem, we will:

  1. Determine the correct position for the new value in the maximum binary tree.
  2. If the new value is greater than the root, it becomes the new root, with the old root as its left child.
  3. If the new value is less than the root, recursively determine its position in the left or right subtree.

Data structures used:

  • A binary tree node structure to represent each node in the maximum binary tree.

The algorithm involves recursion to find the appropriate position for the new value while maintaining the properties of the maximum binary tree.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insertIntoMaxTree(root: TreeNode, val: int) -> TreeNode:
    # If the new value is greater than the current root's value,
    # create a new root with the new value and make the current root its left child
    if val > root.val:
        return TreeNode(val, root, None)
    
    # Otherwise, we need to find the correct position in the tree
    current = root
    while current:
        # If we find a node whose value is less than the new value,
        # we can insert the new value here
        if current.val < val:
            newNode = TreeNode(val, current.left, current.right)
            current.left = newNode
            return root
        # Move to the right child to continue searching
        parent = current
        current = current.right

    # If we reach this point, we can attach the new value to the rightmost node
    parent.right = TreeNode(val)
    return root
← Back to All Questions