Add One Row to Tree

Medium

Asked by:

38 views

Topics:

TreesRecursion

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
cur's original left subtree should be the left subtree of the new left subtree root.
cur's original right subtree should be the right subtree of the new right subtree root.
If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

Example 2:

Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
The depth of the tree is in the range [1, 10⁴].
-100 <= Node.val <= 100
-10⁵ <= val <= 10⁵
1 <= depth <= the depth of tree + 1

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 should I return if the input tree is null?
What are the possible values for `val` and `depth`? Can `val` be null? Can `depth` be zero or negative?
If `depth` is 1, should I replace the entire original tree with the new row, or just make the original tree the left child of the new root?
Is the original tree guaranteed to be a valid binary tree?
If `depth` is greater than the actual depth of the tree, where should the new row be added?

Brute Force Solution

Approach

The brute force approach to adding a row to a tree means we explore every possible place to insert this new row. We essentially check every node in the tree to see if it's where we want to add the new row.

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

Start at the very top node of the tree.
Check if the current level is the correct depth to add the new row. If so, create the new nodes with the specified value, and attach the original node's children to them.
If the current level is not the correct depth, look at the left 'branch' (child) of the current node and repeat the process. Essentially, we're going deeper into the tree.
After exploring the left side fully, explore the right 'branch' (child) of the original node, again repeating the checking and adding process if necessary.
Continue this process for every single node in the tree, ensuring that every possible position for the new row has been considered.

Code Implementation

def add_one_row(root, value, depth):    if depth == 1:
        new_node = TreeNode(value)
        new_node.left = root
        return new_node
    
    def add_row_recursive(node, current_depth):
        if not node:
            return

        if current_depth == depth - 1:
            # Insert new nodes with the given value
            temp_left = node.left

            node.left = TreeNode(value)
            node.left.left = temp_left

            temp_right = node.right

            node.right = TreeNode(value)
            node.right.right = temp_right

        else:
            # Recursively call the method on the left and right subtrees
            add_row_recursive(node.left, current_depth + 1)

            # Now traverse the right sub-tree
            add_row_recursive(node.right, current_depth + 1)

    add_row_recursive(root, 1)
    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node of the tree once to check if the current level is the desired depth to insert the new row. In a tree with n nodes, we traverse each node, performing a constant amount of work at each node to check its depth and potentially insert new nodes. Therefore, the time complexity is directly proportional to the number of nodes, which results in O(n) where n is the number of nodes in the tree.

Space Complexity

O(H) – The described brute force approach uses recursion to traverse the tree. In the worst-case scenario, the recursion will go down to the deepest level of the tree, creating a stack frame for each level. The maximum depth of the recursion stack will therefore be the height (H) of the tree. Therefore, the auxiliary space required for the recursive call stack is proportional to the height of the tree, H. This makes the space complexity O(H).

Optimal Solution

Approach

The key idea is to traverse the tree level by level until we reach the desired depth. At that depth, we insert the new row of nodes with the given value, effectively pushing the original nodes down a level.

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

Start exploring the tree from the very top.
Keep track of how far down the tree you've gone; this is the current depth.
If the current depth is one level before where you want to add the new row, it's time to act.
For each node at that specific depth, create two new nodes with the given value.
Make the original node's left child the left child of the new left node.
Make the original node's right child the right child of the new right node.
Attach the new left node to the left of the original node.
Attach the new right node to the right of the original node.
If the target depth is zero, create new nodes and make the original tree be the left node of the new tree.
If the target depth is not yet reached, continue exploring down to the next level of the tree and repeat the process.

Code Implementation

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

def add_one_row(root, value, depth):
    if depth == 1:
        new_node = TreeNode(value)
        new_node.left = root
        return new_node

    def traverse_tree(node, current_depth):
        if not node:
            return

        if current_depth == depth - 1:
            # We've reached the level above insertion.
            new_left_node = TreeNode(value)
            new_right_node = TreeNode(value)

            new_left_node.left = node.left
            new_right_node.right = node.right

            node.left = new_left_node
            node.right = new_right_node

        else:
            # Continue traversal to reach target depth.
            traverse_tree(node.left, current_depth + 1)
            traverse_tree(node.right, current_depth + 1)

    # Initiate the recursive traversal.
    traverse_tree(root, 1)
    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the tree level by level. In the worst-case scenario, it needs to visit all nodes in the tree to reach the desired depth, where n is the number of nodes in the tree. Inserting the new nodes at the target depth involves a constant amount of work per node at that level. Therefore, the time complexity is determined by the tree traversal, which takes O(n) time, where n is the number of nodes.

Space Complexity

O(W) – The algorithm uses a level-order traversal which implicitly uses a queue to store nodes at each level. In the worst-case scenario, the queue can hold all nodes at the widest level of the tree. Therefore, the auxiliary space complexity is proportional to the maximum width (W) of the tree, where W is the maximum number of nodes at any level. Since the tree can be highly unbalanced, W could approach N in the worst case but is generally less than N.

Edge Cases

Case	How to Handle
Null root	If root is null and depth is 1, return a new tree node with value v as the root, with two children having null values, otherwise return null.
Depth is less than 1	Handle depths less than 1 by either treating it as an error or returning the original root.
Integer overflow when calculating tree size or intermediate values in recursive calls.	Ensure the values used for v, depth, and any calculations within the tree structure stay within integer limits.
Adding row at depth 1 with non-empty tree	Create a new root node with value v and make original tree root the left child of this new root and right child set to null if the original root does not have a right child, otherwise the right child should be set to null.
Large tree depth potentially leading to stack overflow during recursion.	Consider using an iterative approach (e.g., level order traversal) instead of recursion for very deep trees to avoid stack overflow errors.
Skewed tree (all nodes on one side)	The algorithm should handle skewed trees correctly, inserting new nodes at the specified depth regardless of the tree's balance.
Depth greater than height of the tree.	If depth is greater than the height of the tree, the new row will simply not be added, and the original tree will be returned as there is nothing to process at that depth.
Value 'v' is a boundary value close to the maximum or minimum integer possible.	The value being inserted for a node should be validated to ensure insertion does not cause integer overflow issues in subsequent operations.

Null root

How to Handle:

If root is null and depth is 1, return a new tree node with value v as the root, with two children having null values, otherwise return null.

Depth is less than 1

How to Handle:

Handle depths less than 1 by either treating it as an error or returning the original root.

Integer overflow when calculating tree size or intermediate values in recursive calls.

How to Handle:

Ensure the values used for v, depth, and any calculations within the tree structure stay within integer limits.

Adding row at depth 1 with non-empty tree

How to Handle:

Create a new root node with value v and make original tree root the left child of this new root and right child set to null if the original root does not have a right child, otherwise the right child should be set to null.

Large tree depth potentially leading to stack overflow during recursion.

How to Handle:

Consider using an iterative approach (e.g., level order traversal) instead of recursion for very deep trees to avoid stack overflow errors.

Skewed tree (all nodes on one side)

How to Handle:

The algorithm should handle skewed trees correctly, inserting new nodes at the specified depth regardless of the tree's balance.

Depth greater than height of the tree.

How to Handle:

If depth is greater than the height of the tree, the new row will simply not be added, and the original tree will be returned as there is nothing to process at that depth.

Value 'v' is a boundary value close to the maximum or minimum integer possible.

How to Handle:

The value being inserted for a node should be validated to ensure insertion does not cause integer overflow issues in subsequent operations.