998. Maximum Binary Tree II

Problem Description

In this problem, we're given the root node of a maximum binary tree—a kind of binary tree where each node's value is greater than the values of every node in its subtree—and an integer val. Our task is to insert this integer into the maximum binary tree following a specific set of rules without having direct access to the array from which the tree was originally constructed.

To recall, a maximum binary tree is constructed as follows:

If the array a is empty, return null.
Find the largest element in a, let's say it's a[i]. This becomes the root node.
The left child of the root node is another maximum tree constructed from the subarray to the left of a[i], i.e., a[0] to a[i - 1].
The right child is constructed from the subarray to the right of a[i], i.e., a[i + 1] to a[a.length - 1].
The node with the value a[i] becomes the root of this maximum binary tree.

The problem defines an array b, which is a copy of the original array a but with the new integer val added to the end. We must return a maximum binary tree constructed from this new array b, but as we do not have access to a, we must do this by modifying the given tree directly.

Intuition

The key to solving this problem lies in understanding the properties of the maximum binary tree and how the new value val can affect the structure of the tree:

The value val is being appended to the array, so in the resulting maximum binary tree for b, val will either be the new root or a child in the right subtree of the existing tree, as all values in a are to its left and thus cannot be its left child.
If val is greater than the current root's value, then val should become the new root, and the whole existing tree should become the left child of this new root.
If val is less than the current root's value, we need to traverse the right subtree recursively and perform a similar decision process considering val and the value of that subtree's root.
We continue this process recursively until we find the right position for the new value val. If we reach a point where val is larger than the root of a subtree, or we reach a leaf node (which would be None), then we insert val there.

The provided solution translates this intuition into a straightforward recursive function that correctly modifies the existing tree to include the new value.

Learn more about Tree and Binary Tree patterns.

Solution Approach

The solution provided uses a recursive function to insert the new value into the maximum tree. The implementation capitalizes on the recursive tree structure and the definition of a maximum tree to determine the appropriate place for the new value.

Here are the key steps and patterns used in the implementation:

Base Cases:
- When the root passed to the insertIntoMaxTree function is None, this suggests we've reached a point where the new value val should be inserted. Hence, a new node with val is created and returned.
- If val is greater than the root.val, according to the property of a maximum tree, val must be the new root, and the current tree should be the left child of this new node with val.
Recursion:
- If the current root's value is greater than val, we need to insert val into the right subtree of the current root. To do this, the function calls itself recursively with the right child of the root and the val.
Tree Node Construction:
- A new tree node is created with the given val, when needed, by calling TreeNode(val, root) where root would become the left child if val becomes the new root.
Linking Nodes:
- After the recursive call, the return value (which is the modified right subtree with the new value inserted) is linked back to the current root's right child.

By applying these steps, the algorithm maintains the integrity of the maximum tree while inserting the new value in its correct place. Since the algorithm operates directly on the original tree nodes, no additional data structures are needed beyond those provided by the tree itself.

Here's an excerpt of the solution reflecting these steps:

if root is None or root.val < val:
    return TreeNode(val, root)
root.right = self.insertIntoMaxTree(root.right, val)
return root

This code checks whether we have to insert a new root or continue the traversal. The recursive call to self.insertIntoMaxTree(root.right, val) ensures we dive into the right subtree to explore further placement for val.

In this manner, every call of insertIntoMaxTree either creates a new node when it finds the appropriate place for val or navigates through the right subtree to find that place, thus ensuring the new value is added exactly where it should be to preserve the maximum tree property.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example to illustrate the solution approach. Suppose we have a maximum binary tree constructed from the array [3, 2, 1], and we want to insert the value 4.

The existing maximum binary tree looks like this:

    3
   / \
  2   1

In this tree, 3 is the root as it's the largest element in the array. The left subtree consists of 2, and the right subtree consists of 1.

Now, following our rules, we want to insert 4. Since 4 is greater than the current root’s value 3, according to our solution approach, 4 should become the new root of the tree.

According to the solution approach step 1 for Base Cases:

4 being greater than the existing root 3, requires that a new root node be created with 4. The existing tree becomes the left child of this new node.

The updated tree now looks like this:

With 4 as the new root, 3 now becomes the left child, and the previous left and right children (2 and 1 respectively) of 3 remain unchanged.

If we were to insert a value less than 1, for example 0, the flow would be as follows according to our Intuition Step 3 and the Recursive process described in the solution approach:

Since 0 is not greater than the root node 4, we move to the right subtree. However, since 3 (the left child of 4) is also not the right place for 0 as our value needs to go to the right of 3, we proceed to its right subtree.
Comparing 0 to 1 (the right child of 3), 0 is still less, so we move to the right of 1. Since 1 has no right child, we insert 0 as the right child of 1.

Finally, the tree looks like this:

In each step of the above examples, the algorithm recursively traverses the tree to find the right spot for the insertion, always ensuring that the maximum tree property is preserved, which is that the value of each node is greater than all the values in its left subtree and less than any value in its right subtree.

Solution Implementation

1class TreeNode:
2    # Definition for a binary tree node.
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val       # Node's value
5        self.left = left     # Left child
6        self.right = right   # Right child
7
8class Solution:
9    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
10        """
11        Inserts a new value into the Max Tree.
12        A Max Tree is a tree where every node is greater than its children.
13        The new value is always inserted as a leaf node.
14
15        Parameters:
16        root (TreeNode): The root of the original Max Tree.
17        val (int): The value to be inserted.
18
19        Returns:
20        TreeNode: The root of the updated Max Tree.
21        """
22        # If the current node is None or the new value is greater than the current node,
23        # then insert the new value above and to the right of the current node.
24        if root is None or root.val < val:
25            return TreeNode(val, root)
26
27        # Recursively insert the new value into the right subtree.
28        root.right = self.insertIntoMaxTree(root.right, val)
29      
30        # Return the root as it may be unchanged.
31        return root
32

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int value;             // The value contained in the node
6    TreeNode left;         // Reference to the left child
7    TreeNode right;        // Reference to the right child
8
9    // Constructor for creating a leaf node with a specific value
10    TreeNode(int value) {
11        this.value = value;
12    }
13
14    // Constructor for creating a node with a specific value, left and right children
15    TreeNode(int value, TreeNode left, TreeNode right) {
16        this.value = value;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    /**
24     * Inserts a value into a maximum binary tree following the rules:
25     * - Each tree node has a value greater than any of its children.
26     * - Newly inserted value is always added as a new tree node in a position that maintains the maximum tree property.
27     *
28     * @param root the root of the current maximum binary tree
29     * @param val  the value to insert into the tree
30     * @return the root of the modified maximum binary tree
31     */
32    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
33        // If the tree is empty or the value at the root is less than the value to be inserted,
34        // create a new node with the inserted value and the current tree as its left subtree.
35        if (root == null || root.value < val) {
36            return new TreeNode(val, root, null);
37        }
38      
39        // Recursively insert into the right subtree.
40        // Because we are working with a max tree, we go down the tree to the right as long as
41        // we do not find a node with a lesser value where our new node will be inserted.
42        root.right = insertIntoMaxTree(root.right, val);
43      
44        // Return the root of the tree with the new value inserted while keeping its max tree structure.
45        return root;
46    }
47}
48

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    /**
16     * Insert a new value into a Maximum Binary Tree and return the updated tree.
17     * 
18     * A Maximum Binary Tree is a tree where every node has a value greater than 
19     * any value of the nodes in its left subtree and any value of the nodes in its right subtree.
20     * 
21     * @param root The root node of the Maximum Binary Tree.
22     * @param val The value to be inserted into the Maximum Binary Tree.
23     * @return Return the updated tree after inserting the value.
24     */
25    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
26        // If the root is null or the root value is less than the value to be inserted,
27        // then a new node needs to be created with the value, where the current root becomes
28        // the left child of the new node (as per Maximum Binary Tree properties).
29        if (!root || root->val < val) {
30            return new TreeNode(val, root, nullptr);
31        }
32
33        // If the value to be inserted is smaller than the root, traverse the right subtree
34        // to find the spot to insert the new value, since all values in the right subtree
35        // should be smaller than the root.
36        root->right = insertIntoMaxTree(root->right, val);
37
38        // Return the root as the unchanged part of the tree after the insertion.
39        return root;
40    }
41};
42

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    // TreeNode constructor: initializes a TreeNode with given values for val, left and right.
8    // If no value is provided, val defaults to 0 and left/right default to null.
9    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
10        this.val = val;
11        this.left = left;
12        this.right = right;
13    }
14}
15
16// Function to insert a new value into a maximum binary tree.
17// A maximum binary tree is a binary tree where every node has a value greater than any other value in its descendants.
18//
19// Parameters:
20// rootNode: The root node of the current maximum binary tree.
21// newValue: The new value to be inserted into the maximum binary tree.
22// 
23// Returns: The root node of the binary tree after inserting the new value.
24function insertIntoMaxTree(rootNode: TreeNode | null, newValue: number): TreeNode | null {
25    // If the root node is null or the value of the root is less than the new value,
26    // create a new tree node with the new value, with the entire current tree as its left child.
27    if (!rootNode || rootNode.val < newValue) {
28        return new TreeNode(newValue, rootNode);
29    }
30  
31    // Otherwise, recursively attempt to insert the new value into the right subtree.
32    // The result of this recursive call will be assigned as the new right child of the current node.
33    rootNode.right = insertIntoMaxTree(rootNode.right, newValue);
34  
35    // Return the root node as it retains its position.
36    return rootNode;
37}
38

Time and Space Complexity

The time complexity of the code provided is O(N), where N is the number of nodes in the binary tree. We are traversing the tree to find the right place to insert the new node with value val. In the worst case scenario, we insert the node as the rightmost child, which requires traversing all the way down to the bottom of the tree, which can be N nodes in a skewed tree.

The space complexity of the recursive implementation is also O(H), where H is the height of the tree, because of the recursive call stack. In the worst case in a skewed tree (which behaves like a linked list), this would also be O(N). In a balanced tree, the height H would be O(log N) so the space complexity would be O(log N). However, since the tree is formed by inserting nodes into the maximum tree, it can be heavily skewed, so the space complexity can also be considered O(N) in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: