Maximum Binary Tree II

This problem involves a maximum binary tree, where the value of each node is greater than any other value in its subtree. You are given the root of such a tree and an integer val. The task is to insert the value val into the tree in a way that maintains its maximum binary tree property and then return the new root.

A maximum binary tree is constructed from an array a by choosing the largest element to become the root, and then recursively constructing the left and right subtrees using the elements to the left and right of the largest element. Given the root of such a tree and a value val, the task is to append val to the array, re-construct the maximum binary tree, and return the new root.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

class Solution:
    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # If the root is null or val is greater than the root's value, we create a new root node with value val
        if not root or val > root.val:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root

        # If val is less than the root's value, we recursively call the function on the right subtree
        root.right = self.insertIntoMaxTree(root.right, val)
        return root

Explanation

• If the root is null or val is greater than the root’s value, we create a new root node with the value val, and the current root becomes its left child.
• Otherwise, we recursively call the function on the right subtree, setting the result as the right child of the current root.
• Finally, we return the root.

This code takes advantage of the maximum binary tree’s properties to efficiently insert the new value and return the new tree’s root, ensuring that the tree remains a maximum binary tree after the insertion.