Add One Row to Tree

Problem Statement

Given a binary tree's root node and two integers, val and depth, the task is to insert a row of nodes into the tree such that each node in the new row has the value val and is positioned at the specified depth. Remember, the depth of the root node is 1.

To accomplish this, follow these rules:

• For each existing node cur at the depth depth - 1, insert two new tree nodes, both having the value val.
• Set these new nodes as the left and right children of cur. The original left subtree of cur should now branch off the new left node, and similarly, the original right subtree should attach to the new right node.
• In a special case where depth is 1, meaning the new nodes should directly follow the root, transform the current root into the left child of a new root node that holds the value val.

Examples

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, 104].
• The depth of the tree is in the range [1, 104].
• -100 <= Node.val <= 100
• -105 <= val <= 105
• 1 <= depth <= the depth of tree + 1

Approach and Intuition

To successfully add a new row of nodes to a binary tree at a specified depth and with a specific val, let's break down the steps based on whether the new row is to be added at the root or at a deeper level:

1. Determine if the new depth is at the root level:

   • If depth equals 1, create a new root node with the value val. Make the existing tree the left subtree of this new node.
   • This handles cases where inserting a row of nodes directly beneath the very top of the tree, i.e., beneath the root, is required, effectively pushing the entire tree down.

2. Insert the row at a depth other than the root:

   • Employ a breadth-first search (BFS) traversal up to depth - 1.
   • For each node encountered:
     • Initiate two new nodes, both with the value val.
     • Attach the original left child of the current node to the new left node.
     • Attach the original right child of the current node to the new right node.
     • Set these new nodes as the left and right children of the current node, respectively.
   • This approach ensures that we efficiently navigate through the tree to precisely the level right before where the insertion is supposed to occur.

These operations adhere to the constraints and ensure that we are modifying the tree's structure by inserting nodes only where specified, without affecting other portions of the tree's structure or properties.

Solutions

public class Solution {
    public TreeNode insertNewRow(TreeNode root, int value, int depth) {
        if (depth == 1) {
            TreeNode newNode = new TreeNode(value);
            newNode.left = root;
            return newNode;
        }
        Queue<TreeNode> currentLevel = new LinkedList<>();
        currentLevel.add(root);
        int currentDepth = 1;
        while (currentDepth < depth - 1) {
            Queue<TreeNode> nextLevel = new LinkedList<>();
            while (!currentLevel.isEmpty()) {
                TreeNode currNode = currentLevel.poll();
                if (currNode.left != null) nextLevel.add(currNode.left);
                if (currNode.right != null) nextLevel.add(currNode.right);
            }
            currentLevel = nextLevel;
            currentDepth++;
        }
        while (!currentLevel.isEmpty()) {
            TreeNode currNode = currentLevel.poll();
            TreeNode leftNode = currNode.left;
            currNode.left = new TreeNode(value);
            currNode.left.left = leftNode;
            leftNode = currNode.right;
            currNode.right = new TreeNode(value);
            currNode.right.right = leftNode;
        }
        return root;
    }
}