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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Add One Row to Tree

Number: 623

Difficulty: Medium

Paid? No

Companies: Google, Meta, Gilt Groupe

Problem Description

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. If depth is 1, create a new root node with value val and attach the original tree as its left child. Otherwise, for every node at depth - 1, insert two new nodes with value val between the node and its subtrees (the original left subtree becomes the left child of the new left node, and the original right subtree becomes the right child of the new right node).

Key Insights

  • If depth is 1, the problem becomes adding a new root node.
  • Traverse the tree until the level before the target depth (i.e., depth - 1).
  • Utilize either BFS (level-order traversal) or DFS to reach the required level.
  • For each node at depth - 1, insert new nodes and reconnect its children appropriately.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since every node may be visited in the worst-case scenario. Space Complexity: O(n), which accounts for the space needed by the queue in BFS (or the recursive stack in DFS).

Solution

We can solve this problem by performing a Breadth-First Search (BFS) to traverse the tree level by level until reaching the nodes at depth - 1. Once at the correct level, for each node, we create two new nodes with the given value and attach the original left child as the left child of the new left node, and the original right child as the right child of the new right node. A special case is handled when depth is 1 by creating a new root and setting the original tree as its left subtree.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def addOneRow(root, val, depth):
    # Special case: if depth is 1, create a new root node.
    if depth == 1:
        new_root = TreeNode(val)
        new_root.left = root
        return new_root

    # Use BFS to traverse the tree.
    queue = [root]
    current_depth = 1

    # Traverse until the level before the target depth.
    while queue:
        if current_depth == depth - 1:
            # Insert new nodes for each node in the current level.
            for node in queue:
                temp_left = node.left
                temp_right = node.right
                node.left = TreeNode(val)
                node.left.left = temp_left
                node.right = TreeNode(val)
                node.right.right = temp_right
            break
        
        next_level = []
        for node in queue:
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        queue = next_level
        current_depth += 1

    return root

# Example usage:
# Construct tree: [4,2,6,3,1,5]
root = TreeNode(4)
root.left = TreeNode(2, TreeNode(3), TreeNode(1))
root.right = TreeNode(6, TreeNode(5))
result = addOneRow(root, 1, 2)
← Back to All Questions