This question consists of simple problem with multiple ways to solve this. I like recursion so I decided to go with that approach. The question doesn't seem to have many edge cases so if you are getting correct answer for the example test cases and a little variation to them, you will get your submission approved easily.

**Difficulty:** Medium

**Jump To:**

## Problem Statement

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.

**Example 1:**

```
Input:
A binary tree as following:
4
/ \
2 6
/ \ /
3 1 5
v = 1
d = 2
Output:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
```

**Example 2:**

```
Input:
A binary tree as following:
4
/
2
/ \
3 1
v = 1
d = 3
Output:
4
/
2
/ \
1 1
/ \
3 1
```

**Note:**

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

## Explanation

So the problem is quite simple, You are given a non-empty binary tree and a value `v`

which needs to be inserted as a child at depth `d`

for all non-empty parent nodes. The new node will be at both left and right edge of the parent. The child nodes/subtree of the parent need to be set as the child of the newly created node with the same direction left/right. This should be clear with the given examples.

## Solution

We are going to do only the below things:

- If
`depth=1`

i.e. we need to add the value at root, then we just need to create a new node with value`v`

and make the current`root`

its left child and return the pointer to the new node. - We need to traverse the tree in both directions (left/right) till we reach the depth
`d-1`

. Let's say we are at the node`parent`

, this is the node below which the new nodes need to be added. - Now we need to create a new node for the left subtree of
`parent`

so this new node's left pointer will point to the left subtree of`parent`

and then we'll make`parent`

's left pointer point to the new node. That's how we have added a node between the`parent`

and left subtree. - Same needs to be done for the right subtree.

As we'll be going down to the tree, we can call it DFS(Depth First Search) based on recursion. So **Time Complexity:** of this solution may go to `O(n)`

as we might need to add the nodes below the leaf. As recursion uses stack so the **Space Complexity:** can be `O(n)`

in the worst case.

## Implementation

**C++ Code:**

```
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
// If need to add the row on root
if(d==1){
// Just create a new node with value v
// and current root as left child
TreeNode *ptr = new TreeNode(v, root, nullptr);
return ptr;
}
// Traverse down to the parent node at depth d-1
// to add row at depth d(>1)
addRow(root, v, d-1);
// Return same pointer root with modified tree
return root;
}
// Function to traverse down to the depth d-1 and add row
void addRow(TreeNode* parent, int v, int dep){
// If node is NULL the do nothing
if(!parent)
return;
// If we have reached depth d-1 i.e. dep=1
if(dep==1){
TreeNode *temp;
// Store left ptr
temp = parent->left;
// Replace left ptr with new node with value v
parent->left = new TreeNode(v);
// Set stored left pointer as new node's left ptr
parent->left->left = temp;
// Store right ptr
temp = parent->right;
// Replace right ptr with new node with value v
parent->right = new TreeNode(v);
// Set stored right pointer as new node's right ptr
parent->right->right = temp;
}
// Else go deeper
else{
addRow(parent->left, v, dep-1);
addRow(parent->right, v, dep-1);
}
}
};
```

**Runnable C++ Code:**

## Discussion (0)