Solution: Add One Row to Tree
Tags: algorithms, javascript, java, python
Published: 2021-03-09 09:51:23

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/add-one-row-to-tree/discuss/1101083).*

---

#### [Leetcode Problem #623 (*Medium*): Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|A binary tree as following:<br>![Example 1 Input](https://i.imgur.com/v1libpS.png)<br>v = 1<br>d = 2
Output:|![Example 1 Output](https://i.imgur.com/7LOeTa4.png)
>
Example 2:||
|---:|---|
Input:|A binary tree as following:<br>![Example 1 Input](https://i.imgur.com/BHh3UVh.png)<br>v = 1<br>d = 3
Output:|![Example 1 Output](https://i.imgur.com/GRf3Uvf.png)

---

#### ***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.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

We could definitely solve this a number of ways, but I'm always partial to **recursion** when possible, especially when you can simply recurse the main function rather than having to define a separate recursive helper function. The recursive route is a **depth-first search** (**DFS**) **solution**.

We can use the depth variable (**d**) as a countdown of sorts, decrementing it as we traverse downward through the tree until we get to our destination row. Since we're going to need to attach the new nodes at **d** to their parents, we should actually perform our operations when **d = 2**, rather than **d = 1**, so that we have access to the parent node.

This also allows us to deal with the sticky edge case of when the original value of **d** is **1**. Since no parent exists for the original **root**, we'll have to just create our new node and attach the **root** to it before **returning**. This can only ever happen on the initial function call, as otherwise we will never reach **d = 1** in any later recursion.

The function will **return** the node each recursion, but since we're not doing anything with the return value when the the function is called internally, it will only really be meaningful on the original function call.

This works because we're passing **node references** through the recursion, so the tree object is being modified regardless of return values.

---

#### ***Implementation:***

The code is almost identical between all four languages.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var addOneRow = function(root, v, d) {
    if (d === 1) return new TreeNode(v, root, null)
    if (d === 2) {
        root.left = new TreeNode(v, root.left, null)
        root.right = new TreeNode(v, null, root.right)
    } else {
        if (root.left) addOneRow(root.left, v, d-1)
        if (root.right) addOneRow(root.right, v, d-1)
    }
    return root
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
        if d == 1: return TreeNode(v, root, None)
        elif d == 2:
            root.left = TreeNode(v, root.left, None)
            root.right = TreeNode(v, None, root.right)
        else:
            if root.left: self.addOneRow(root.left, v, d-1)
            if root.right: self.addOneRow(root.right, v, d-1)
        return root
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if (d == 1) return new TreeNode(v, root, null);
        else if (d == 2) {
            root.left = new TreeNode(v, root.left, null);
            root.right = new TreeNode(v, null, root.right);
        } else {
            if (root.left != null) addOneRow(root.left, v, d-1);
            if (root.right != null) addOneRow(root.right, v, d-1);
        }
        return root;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if (d == 1) return new TreeNode(v, root, NULL);
        else if (d == 2) {
            root->left = new TreeNode(v, root->left, NULL);
            root->right = new TreeNode(v, NULL, root->right);
        } else {
            if (root->left) addOneRow(root->left, v, d-1);
            if (root->right) addOneRow(root->right, v, d-1);
        }
        return root;
    }
};
```