623. Add One Row to Tree

[mah-shamim]

Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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:

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

• 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

[basharul-siddike]

We can use either Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the tree. The idea is to add the new row at the specified depth.

Approach:

1. Edge Case: If the depth is 1, we need to add the new node as the new root of the tree.
2. DFS or BFS: Traverse the tree to reach nodes at depth - 1, then:
   • Insert new nodes with value val as left and right children of each node.
   • The original left child of the node becomes the left child of the newly inserted left node.
   • Similarly, the original right child becomes the right child of the newly inserted right node.

Steps:

1. If depth == 1, create a new root and attach the original tree as the left child of the new root.
2. Otherwise, traverse the tree until the current depth is depth - 1.
3. At each node, insert new nodes as described.

Let's implement this solution in PHP: 623. Add One Row to Tree

<?php
// 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;
    }
}

function addOneRow($root, $val, $depth) {
    if ($depth == 1) {
        // Create a new root with value $val, and set the original tree as its left child
        return new TreeNode($val, $root, null);
    }

    // Perform BFS to find nodes at depth - 1
    $queue = [$root];
    $current_depth = 1;

    // Traverse until we reach depth - 1
    while (!empty($queue) && $current_depth < $depth - 1) {
        $size = count($queue);
        for ($i = 0; $i < $size; $i++) {
            $node = array_shift($queue);
            if ($node->left !== null) {
                $queue[] = $node->left;
            }
            if ($node->right !== null) {
                $queue[] = $node->right;
            }
        }
        $current_depth++;
    }

    // At this point, we are at depth - 1. Add the new row.
    foreach ($queue as $node) {
        // Save the original left and right children
        $old_left = $node->left;
        $old_right = $node->right;

        // Insert new nodes with value $val
        $node->left = new TreeNode($val, $old_left, null);
        $node->right = new TreeNode($val, null, $old_right);
    }

    return $root;
}

// Helper function to print the tree in level order for visualization
function printTree($root) {
    $result = [];
    $queue = [$root];
    while (!empty($queue)) {
        $node = array_shift($queue);
        if ($node !== null) {
            $result[] = $node->val;
            $queue[] = $node->left;
            $queue[] = $node->right;
        } else {
            $result[] = null;
        }
    }
    // Remove trailing null values
    while (end($result) === null) {
        array_pop($result);
    }
    return $result;
}

// Test case 1
$root = new TreeNode(4, 
            new TreeNode(2, new TreeNode(3), new TreeNode(1)), 
            new TreeNode(6, new TreeNode(5), null));
$val = 1;
$depth = 2;
$new_tree = addOneRow($root, $val, $depth);
print_r(printTree($new_tree)); // Output should be [4, 1, 1, 2, null, null, 6, 3, 1, 5]

// Test case 2
$root = new TreeNode(4, 
            new TreeNode(2, new TreeNode(3), new TreeNode(1)), 
            null);
$val = 1;
$depth = 3;
$new_tree = addOneRow($root, $val, $depth);
print_r(printTree($new_tree)); // Output should be [4, 2, null, 1, 1, 3, null, null, 1]
?>

Explanation:

1. Edge case (depth == 1): We create a new root node with the value val and set the original root as the left child of this new root. This is handled right at the start of the function.

2. BFS traversal: We traverse the tree level by level using a queue until we reach nodes at depth depth - 1. These are the nodes where we will insert the new row.

3. Inserting new row: For each node at depth - 1, we create two new nodes with value val. The original left child of the node becomes the left child of the new left node, and the original right child becomes the right child of the new right node.

Time Complexity:

• Traversing the tree requires (O(n)) where (n) is the number of nodes in the tree.
• Since we perform BFS until depth depth - 1 and update each node at that depth, the time complexity is linear in the number of nodes: (O(n)).

Test Cases:

1. Example 1:

   Input: root = [4,2,6,3,1,5], val = 1, depth = 2
   Output: [4,1,1,2,null,null,6,3,1,5]

2. Example 2:

   Input: root = [4,2,null,3,1], val = 1, depth = 3
   Output: [4,2,null,1,1,3,null,null,1]

This solution ensures that the tree is modified correctly according to the problem's rules.

[mah-shamim]

Thanks to solve the problem of adding a row of nodes at a given depth in a binary tree

[basharul-siddike]

Thanks