> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/601-700/add-one-row-to-tree.md).

# 623. Add One Row to Tree

### Description

Given the root of a binary tree, then value `v` and depth `d`, you need to add a row of nodes with value `v` at the given depth `d`. The root node is at depth 1.

The adding rule is: given a positive integer depth `d`, for each NOT null tree nodes `N` in depth `d-1`, create two tree nodes with value `v` as `N's` left subtree root and right subtree root. And `N's` **original left subtree** should be the left subtree of the new left subtree root, its **original right subtree** should be the right subtree of the new right subtree root. If depth `d` is 1 that means there is no depth d-1 at all, then create a tree node with value **v** as the new root of the whole original tree, and the original tree is the new root's left subtree.

### Constraints

* The given d is in range \[1, maximum depth of the given tree + 1].
* The given binary tree has at least one tree node.

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/add-one-row-to-tree/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[4, 2, 6, 3, 1, 5], v=1, d=2

<div align="left"><img src="/files/-MVN6nnZtKlcvkUc617O" alt=""></div>

**Output:** \[4, 1, 1, 2, null, null, 6, 3, 1, 5]

<div align="left"><img src="/files/-MVN6fDzdmW2DqEsO-PA" alt=""></div>
{% endtab %}

{% tab title="Example 2" %}
**Input:** \[4, 2, null, 3, 1], v=1, d=3

<div align="left"><img src="/files/-MVN6BKiudI4fCSqeyoU" alt=""></div>

**Output:** \[4, 2, null, 1, 1, 3, null, null, 1]

<div align="left"><img src="/files/-MVN6MSS-SAAdU4eUg4M" alt=""></div>
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```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;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n). A total of n nodes of the given tree 
 *    will be considered.
 * Space complexity : O(n). The depth of the recursion tree can go upto n 
 *    in the worst case(skewed tree).
 */

class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if(d == 1) {
            TreeNode node = new TreeNode(v);
            node.left = root;
            return node;
        }
        addOneRowHelper(root, v, d, 1);
        return root;
    }
    
    private void addOneRowHelper(TreeNode root, int v, int depth, int currDepth) {
        if(root == null) {
            return;
        }
        if(currDepth < depth-1) {
            addOneRowHelper(root.left, v, depth, currDepth+1);
            addOneRowHelper(root.right, v, depth, currDepth+1);
        }
        if(currDepth == depth-1) {
            TreeNode left = root.left;
            TreeNode right = root.right;
            root.left = new TreeNode(v);
            root.right = new TreeNode(v);
            root.left.left = left;
            root.right.right = right;
        }
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n). A total of n nodes of the given tree 
 *    will be considered.
 * Space complexity : O(n). The depth of the recursion tree can go upto n 
 *    in the worst case(skewed tree).
 */
 
 public class Solution {
    class Node{
        Node(TreeNode n,int d){
            node=n;
            depth=d;
        }
        TreeNode node;
        int depth;
    }
    
    public TreeNode addOneRow(TreeNode t, int v, int d) {
        if (d == 1) {
            TreeNode n = new TreeNode(v);
            n.left = t;
            return n;
        } 
        Stack<Node> stack=new Stack<>();
        stack.push(new Node(t,1));
        while(!stack.isEmpty())
        {
            Node n=stack.pop();
            if(n.node==null)
                continue;
            if (n.depth == d - 1 ) {
                TreeNode temp = n.node.left;
                n.node.left = new TreeNode(v);
                n.node.left.left = temp;
                temp = n.node.right;
                n.node.right = new TreeNode(v);
                n.node.right.right = temp;
                
            } else{
                stack.push(new Node(n.node.left, n.depth + 1));
                stack.push(new Node(n.node.right, n.depth + 1));
            }
        }
        return t;
    }
}

```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : O(n). A total of n nodes of the given tree will 
 *    be considered in the worst case.
 * Space complexity : O(x). The size of the queuequeue or temp queue can 
 *    grow upto x only. Here, x refers to the number of maximum number 
 *    of nodes at any level in the given tree.
 */

public class Solution {
    public TreeNode addOneRow(TreeNode t, int v, int d) {
        if (d == 1) {
            TreeNode n = new TreeNode(v);
            n.left = t;
            return n;
        }
        Queue < TreeNode > queue = new LinkedList < > ();
        queue.add(t);
        int depth = 1;
        while (depth < d - 1) {
            Queue < TreeNode > temp = new LinkedList < > ();
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove();
                if (node.left != null) temp.add(node.left);
                if (node.right != null) temp.add(node.right);
            }
            queue = temp;
            depth++;
        }
        while (!queue.isEmpty()) {
            TreeNode node = queue.remove();
            TreeNode temp = node.left;
            node.left = new TreeNode(v);
            node.left.left = temp;
            temp = node.right;
            node.right = new TreeNode(v);
            node.right.right = temp;
        }
        return t;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*