623. Add One Row to Tree
Tags: php, algorithms, programming, leetcode
Published: 2024-04-16 19:41:15

623\. Add One Row to Tree

Medium

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

![addrow-tree](https://assets.leetcode.com/uploads/2021/03/15/addrow-tree.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:**

![add2-tree](https://assets.leetcode.com/uploads/2021/03/11/add2-tree.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 <code>[1, 10<sup>4</sup>]</code>.
- The depth of the tree is in the range <code>[1, 10<sup>4</sup>]</code>.
- `-100 <= Node.val <= 100`
- `-105 <= val <= 105`
- `1 <= depth <= the depth of tree + 1`

**Solution**

```
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $val
     * @param Integer $depth
     * @return TreeNode
     */
    function addOneRow($root, $val, $depth) {
         return $this->dfs($root, $val, $depth, 1, false);
    }
    
    function dfs($root, $val, $depth, $curr, $isLeft) {
        if ($root == null) {
            if ($depth == 1) {
                $root = new TreeNode($val);
            }
            return $root;
        }
        
        if ($depth == 1 && $root != null) {
            $newNode = new TreeNode($val);
            $newNode->left = $root;
            $root = $newNode;
            return $newNode;
        }
        
        if ($curr + 1 == $depth) {
            $newNode = new TreeNode($val);
            $newNode->left = $root->left;
            $root->left = $newNode;
            
            $newNode1 = new TreeNode($val);
            $newNode1->right = $root->right;
            $root->right = $newNode1;
            
            return $root;
        }
        
        $this->dfs($root->left, $val, $depth, $curr + 1, true);
        $this->dfs($root->right, $val, $depth, $curr + 1, false);
        return $root;
    }
}

```

**Contact Links**

- **[LinkedIn](https://www.linkedin.com/in/arifulhaque/)**
- **[GitHub](https://github.com/mah-shamim)**