Maximum Binary Tree II

Medium

Asked by:

15 views

Topics:

TreesRecursion

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the binary tree can hold? Can they be negative, zero, or floating-point numbers?
Can the input binary tree be empty (null), or are we guaranteed to have at least one node?
If there are multiple ways to insert the node while maintaining the binary search tree property, is there a specific insertion location that is preferred, or can I choose any valid location?
Is the input tree guaranteed to be a valid binary search tree before the insertion, or do I need to validate that first?
Does the new node's value already exist in the tree, and if so, what should the insertion behavior be? Should I insert it in the left subtree of the equal node, the right subtree, or is it an error?

Brute Force Solution

Approach

With the brute force method, we're exploring every possible way to insert the new value into the binary tree. We build a new tree for each possibility and then compare them to see which one fits the requirements of a maximum binary tree.

Here's how the algorithm would work step-by-step:

First, consider inserting the new value at the very beginning - make it the new root.
Next, imagine placing the new value in every possible location within the tree - every left and right branch.
For each potential location, build a completely new binary tree with the new value inserted there.
Check if the newly built tree fulfills the maximum binary tree property - meaning each node is greater than all its descendants.
If it doesn't satisfy the maximum binary tree condition, discard it.
Out of all the trees that are valid maximum binary trees, choose the 'best' one according to some criteria (for example, the one that results in the smallest height or the one with the least changes from the original tree).

Code Implementation

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

def construct_maximum_binary_tree_brute_force(root, value_to_insert):

    possible_trees = []

    # Inserting new node as root.
    new_root = TreeNode(value_to_insert, root, None)
    if is_maximum_binary_tree(new_root):
        possible_trees.append(new_root)

    # Helper function to generate trees by insertion
    def generate_trees(node, value_to_insert):
        if not node:
            return [None]

        # Insert to the left
        old_left = node.left
        node.left = TreeNode(value_to_insert, old_left, None)

        if is_maximum_binary_tree(root):
            possible_trees.append(copy_tree(root))

        node.left = old_left # revert

        # Insert to the right
        old_right = node.right
        node.right = TreeNode(value_to_insert, old_right, None)

        if is_maximum_binary_tree(root):
            possible_trees.append(copy_tree(root))

        node.right = old_right # revert

        generate_trees(node.left, value_to_insert)
        generate_trees(node.right, value_to_insert)

    generate_trees(root, value_to_insert)

    # Return the first valid tree or None if none is valid
    if not possible_trees:
        return None
    return possible_trees[0]

def is_maximum_binary_tree(root):
    if not root:
        return True

    if root.left and root.value <= root.left.value:
        return False
    if root.right and root.value <= root.right.value:
        return False

    return is_maximum_binary_tree(root.left) and is_maximum_binary_tree(root.right)

def copy_tree(root):
    if not root:
        return None
    new_node = TreeNode(root.value)
    new_node.left = copy_tree(root.left)
    new_node.right = copy_tree(root.right)
    return new_node

# Below is test scaffolding - not part of the solution
# Create the tree: [3,2,1,null,null,null,null]
# root = TreeNode(3)
# root.left = TreeNode(2)
# root.right = TreeNode(1)
#
# new_root = construct_maximum_binary_tree_brute_force(root, 5)
#
# def print_tree(root):
#     if root:
#         print(root.value)
#         print_tree(root.left)
#         print_tree(root.right)
# print_tree(new_root)

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible insertion points for the new value within the tree. In the worst case, this involves considering inserting the new node at the root and then at every possible internal node location. For each insertion point, a new binary tree is constructed which can take O(n) time, and the maximum binary tree property needs to be verified which also could take O(n) time. Since there are n potential places to insert the value and creating/validating the tree can cost O(n), the overall number of possibilities to explore grows factorially with the number of nodes. Therefore, the time complexity is O(n!).

Space Complexity

O(N) – The brute force approach, as described, explores every possible insertion point, building a completely new binary tree for each potential location. In the worst case, each new tree may have all the original nodes of the input tree, plus the new node. Therefore, for a tree with N nodes, creating a new tree requires O(N) space. The space complexity is thus driven by the memory needed to create these temporary binary trees, leading to O(N) space complexity.

Optimal Solution

Approach

The problem involves inserting a new value into an existing 'maximum binary tree' while maintaining its structure. The core idea is to leverage the properties of maximum binary trees: each node is larger than its descendants. By understanding that, we can find the correct insertion point quickly.

Here's how the algorithm would work step-by-step:

Think of the tree as built by always selecting the largest remaining value as the root at each step.
Start at the root of the tree.
Compare the new value we want to insert with the root's value.
If the new value is larger than the root's value, it becomes the new root, and the old tree becomes its left subtree.
If the new value is smaller than the root's value, we need to find the correct spot within the right subtree to insert it.
To find the correct spot, repeat the comparison process in the right subtree. If the new value is bigger than a node in the right subtree, the new value takes its place, and the old node becomes the left child of the new value.
Keep going down the right subtree, performing this comparison, until we find a place where the new value is bigger, or we reach the end of the right subtree.
By selectively moving down the right subtree and understanding the properties of a maximum binary tree, we insert the new value at the appropriate position to keep the tree a valid maximum binary tree.

Code Implementation

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

def insertIntoMaxTree(root, value_to_insert):
    new_node = TreeNode(value_to_insert)

    # If the new value is greater than the root, 
    # it becomes the new root.
    if not root or value_to_insert > root.val:
        new_node.left = root
        return new_node

    current_node = root

    # Traverse down the right subtree to find
    # the correct insertion point
    while current_node.right:
        if value_to_insert > current_node.right.val:
            new_node.left = current_node.right
            current_node.right = new_node
            return root
        current_node = current_node.right

    # If we reach the end of the right subtree,
    # insert the new node here.
    current_node.right = new_node
    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses down only the right subtree of the maximum binary tree. In the worst-case scenario, the tree is heavily skewed to the left, resembling a linked list where each node only has a right child (except possibly the last one). In this case, inserting the new value might require traversing the entire right 'spine' of the tree, which could contain up to n nodes where n is the number of nodes in the tree. Therefore, the time complexity is proportional to the height of the right subtree, which can be at most n, leading to a time complexity of O(n).

Space Complexity

O(H) – The space complexity is primarily determined by the recursive call stack. In the worst-case scenario, the new value is smaller than all nodes, leading to recursive calls traversing down the right subtree until a leaf is reached. The maximum depth of this traversal, and thus the maximum depth of the call stack, is equivalent to the height (H) of the tree. Therefore, the auxiliary space required for the call stack is O(H), where H is the height of the tree. In the worst case, a skewed tree would result in H = N, where N is the number of nodes.

Edge Cases

Case	How to Handle
Null root or null node to insert	Handle null root by creating a new tree with the new node as the root, and handle null node-to-insert as invalid input
Empty Tree (root is None) inserting at root	Create a new TreeNode as the root and return it, making it the new root of the tree.
Inserting a value smaller than the minimum value in the tree	Insert the node at the leftmost position to maintain the BST property, as it will be the smallest element.
Inserting a value larger than the maximum value in the tree	Insert the node at the rightmost position to maintain the BST property, as it will be the largest element.
Tree with only one node and inserting smaller/larger value	Insert the new node as the left/right child respectively, handling both cases to preserve BST properties
Inserting a duplicate value; BST with duplicates allowed (insert on the right to avoid infinite loop)	Insert the duplicate node to the right of the existing node to avoid infinite loops and maintain a relatively balanced tree in the presence of duplicates.
Integer overflow in large or deeply skewed trees	Use appropriate data types (e.g., long) and consider using iterative insertion to avoid potential stack overflow with very deep trees.
Tree structure severely unbalanced after multiple insertions causing O(n) lookup	Consider using self-balancing tree structures (e.g., AVL, Red-Black) for better performance on average and worst-case insert

Null root or null node to insert

How to Handle:

Handle null root by creating a new tree with the new node as the root, and handle null node-to-insert as invalid input

Empty Tree (root is None) inserting at root

How to Handle:

Create a new TreeNode as the root and return it, making it the new root of the tree.

Inserting a value smaller than the minimum value in the tree

How to Handle:

Insert the node at the leftmost position to maintain the BST property, as it will be the smallest element.

Inserting a value larger than the maximum value in the tree

How to Handle:

Insert the node at the rightmost position to maintain the BST property, as it will be the largest element.

Tree with only one node and inserting smaller/larger value

How to Handle:

Insert the new node as the left/right child respectively, handling both cases to preserve BST properties

Inserting a duplicate value; BST with duplicates allowed (insert on the right to avoid infinite loop)

How to Handle:

Insert the duplicate node to the right of the existing node to avoid infinite loops and maintain a relatively balanced tree in the presence of duplicates.

Integer overflow in large or deeply skewed trees

How to Handle:

Use appropriate data types (e.g., long) and consider using iterative insertion to avoid potential stack overflow with very deep trees.

Tree structure severely unbalanced after multiple insertions causing O(n) lookup

How to Handle:

Consider using self-balancing tree structures (e.g., AVL, Red-Black) for better performance on average and worst-case insert