# Add One Row to Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/add-one-row-to-tree)
Canonical: https://scaleengineer.com/dsa/problems/add-one-row-to-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/add-one-row-to-tree/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/add-one-row-to-tree/image1.jpg) 

**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`

# Approaches
## Recursive Depth-First Search (DFS)
This approach uses recursion to traverse the tree. A helper function is used which keeps track of the current depth. When it reaches the target depth (`depth - 1`), it performs the insertion of the new row.
**Time:** O(N), where N is the number of nodes in the tree. In the worst case, we might have to visit all nodes to find the nodes at `depth - 1`. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be O(N), where N is the number of nodes.
**Pros:** Conceptually simple and often leads to concise code for tree traversals.; Can be more space-efficient than BFS for wide, shallow trees.
**Cons:** Can lead to a `StackOverflowError` for extremely deep trees.; May be less space-efficient than BFS for skewed trees where the height H is close to the number of nodes N.
### Explanation
This approach traverses the tree using recursion. A helper function, `insert`, is defined which takes the current node, the value to insert, the target depth, and the current depth as arguments. The base case for the recursion is when the current node is `null`. The main logic is executed when the `currentDepth` reaches `depth - 1`. At this point, the new row is inserted by creating two new nodes and rewiring the `left` and `right` pointers of the current node. The original subtrees are then attached to the newly created nodes. If the `currentDepth` is less than `depth - 1`, the function calls itself on the left and right children, incrementing the `currentDepth`. The special case of `depth = 1` is handled separately in the main function by creating a new root and attaching the original tree as its left child.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        insert(root, val, depth, 1);
        return root;
    }

    private void insert(TreeNode node, int val, int depth, int currentDepth) {
        if (node == null) {
            return;
        }

        if (currentDepth == depth - 1) {
            TreeNode tempLeft = node.left;
            TreeNode tempRight = node.right;

            node.left = new TreeNode(val);
            node.right = new TreeNode(val);

            node.left.left = tempLeft;
            node.right.right = tempRight;
            return; // Pruning the traversal
        }

        insert(node.left, val, depth, currentDepth + 1);
        insert(node.right, val, depth, currentDepth + 1);
    }
}
```
### Algorithm
*   Handle the edge case where `depth` is 1. Create a new root with the given `val`, make the original tree its left child, and return the new root.
*   If `depth` is not 1, call a recursive helper function `insert(root, val, depth, 1)`.
*   The `insert` function takes the current node, value, target depth, and current depth.
*   If the current node is `null`, return.
*   If `currentDepth == depth - 1`, this is the parent level. Modify its children:
    *   Store the original left and right children.
    *   Create new nodes with `val` and set them as the new left and right children.
    *   Attach the original left subtree to the new left node's left child.
    *   Attach the original right subtree to the new right node's right child.
    *   Return to stop traversing deeper.
*   Otherwise, recursively call `insert` for the left and right children with `currentDepth + 1`.

## Iterative Breadth-First Search (BFS)
This approach uses a queue to perform a level-by-level traversal of the tree. It iterates down to the level `depth - 1` and then modifies the nodes at that level to insert the new row.
**Time:** O(N), where N is the number of nodes in the tree. We visit each node up to `depth - 1` once. · **Space:** O(W), where W is the maximum width of the tree. This space is for the queue. In the worst case of a complete binary tree, W can be O(N), where N is the number of nodes.
**Pros:** Avoids recursion and potential stack overflow issues, making it more robust for very deep trees.; Generally more space-efficient for skewed trees where the width is small.
**Cons:** Can be less space-efficient than DFS for very wide trees (e.g., complete binary trees).; The code can be slightly more verbose than the recursive DFS version.
### Explanation
This approach uses a queue to perform a level-order traversal, which is a natural fit for depth-based problems. After handling the `depth = 1` edge case, we populate a queue with the root. We then traverse level by level until we reach the `depth - 1` level. The nodes at this level are the parents for the new row we need to add. The outer loop runs `depth - 2` times to bring us to the correct level. Once at the `depth - 1` level, all nodes at this level will be in the queue. We then iterate through the nodes in the queue, and for each node, we perform the insertion logic: save its original children, create two new nodes with the given value, attach them as the new children, and then re-attach the original subtrees to the new nodes.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int currentDepth = 1;

        // Traverse to the level just before the target depth
        while (currentDepth < depth - 1) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            currentDepth++;
        }

        // Now the queue contains all nodes at depth - 1
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode tempLeft = node.left;
            TreeNode tempRight = node.right;

            node.left = new TreeNode(val);
            node.right = new TreeNode(val);

            node.left.left = tempLeft;
            node.right.right = tempRight;
        }

        return root;
    }
}
```
### Algorithm
*   Handle the edge case where `depth` is 1. Create a new root with the given `val`, make the original tree its left child, and return the new root.
*   Initialize a queue with the `root` node.
*   Use a loop to traverse the tree level by level until `currentDepth` reaches `depth - 1`.
*   Inside the loop, process all nodes at the current level by dequeuing them and enqueuing their non-null children.
*   After the loop, the queue will contain all nodes at level `depth - 1`.
*   Iterate through the nodes in the queue:
    *   For each node, store its original left and right children.
    *   Create new nodes with `val` and set them as the new left and right children.
    *   Attach the original left subtree to the new left node's left child.
    *   Attach the original right subtree to the new right node's right child.
*   Return the original `root`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int val ; private int depth ; public TreeNode addOneRow ( TreeNode root , int val , int depth ) { if ( depth == 1 ) { return new TreeNode ( val , root , null ); } this . val = val ; this . depth = depth ; dfs ( root , 1 ); return root ; } private void dfs ( TreeNode root , int d ) { if ( root == null ) { return ; } if ( d == depth - 1 ) { TreeNode l = new TreeNode ( val , root . left , null ); TreeNode r = new TreeNode ( val , null , root . right ); root . left = l ; root . right = r ; return ; } dfs ( root . left , d + 1 ); dfs ( root . right , d + 1 ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int val ; int depth ; TreeNode * addOneRow ( TreeNode * root , int val , int depth ) { if ( depth == 1 ) return new TreeNode ( val , root , nullptr ); this -> val = val ; this -> depth = depth ; dfs ( root , 1 ); return root ; } void dfs ( TreeNode * root , int d ) { if ( ! root ) return ; if ( d == depth - 1 ) { auto l = new TreeNode ( val , root -> left , nullptr ); auto r = new TreeNode ( val , nullptr , root -> right ); root -> left = l ; root -> right = r ; return ; } dfs ( root -> left , d + 1 ); dfs ( root -> right , d + 1 ); } };
```

### Python

```python
# 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 class Solution : def addOneRow ( self , root : Optional [ TreeNode ], val : int , depth : int ) -> Optional [ TreeNode ]: def dfs ( root , d ): if root is None : return if d == depth - 1 : root . left = TreeNode ( val , root . left , None ) root . right = TreeNode ( val , None , root . right ) return dfs ( root . left , d + 1 ) dfs ( root . right , d + 1 ) if depth == 1 : return TreeNode ( val , root ) dfs ( root , 1 ) return root
```