LeetCode 623 - Add One Row to Tree

The problem asks us to modify a binary tree by adding a new row of nodes with a given value val at a specified depth depth. The input consists of the root of a binary tree, the integer value val to insert, and the target depth depth.

leetcodemediumtreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 623

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to modify a binary tree by adding a new row of nodes with a given value val at a specified depth depth. The input consists of the root of a binary tree, the integer value val to insert, and the target depth depth. Depth is defined such that the root of the tree is at depth 1.

If depth is 1, we do not have a "depth-1" parent node to attach new nodes to, so the new node becomes the new root, and the original tree becomes its left subtree. Otherwise, for each node at depth depth - 1, we insert two new nodes as its children, with the original children becoming the children of these new nodes. The tree structure is preserved below the inserted row.

Constraints indicate that the tree can have up to 10^4 nodes and depths up to 10^4. Node values range from -100 to 100, while the new row value can be -10^5 to 10^5. This ensures that recursion depth may be a consideration in Python due to default recursion limits.

Important edge cases include adding at the root (depth == 1), trees with only left or only right children, and trees where the depth equals the maximum depth plus one.

Approaches

A brute-force approach would traverse the tree completely, visiting every node, and check for nodes at depth - 1. For each qualifying node, we would create new left and right children with value val and attach the original children accordingly. This works correctly but is not conceptually optimal in traversal style; a simple recursive DFS works well, but BFS may be more intuitive for level-based insertion.

The key insight is that we do not need to traverse the entire tree for nodes below depth - 1. A level-order traversal (BFS) allows stopping exactly at depth - 1 and inserting the new nodes efficiently. DFS can also work, stopping recursion once the target depth is reached.

Approach Time Complexity Space Complexity Notes
Brute Force DFS O(N) O(H) Recursively visits each node, inserts new nodes at depth depth. H is tree height.
BFS / Optimal O(N) O(W) Level-order traversal stops at depth-1, uses queue. W is max width of tree.

Algorithm Walkthrough

  1. Handle the edge case depth == 1 first: create a new node with value val, set its left child to the original root, and return this new node as the new root.
  2. Initialize a queue with the root node and current depth as 1.
  3. Perform a level-order traversal until reaching nodes at depth - 1.
  4. For each node at depth - 1, create a new left node and a new right node with value val.
  5. Set the original left child of the current node as the left child of the new left node.
  6. Set the original right child of the current node as the right child of the new right node.
  7. Attach the new nodes to the current node.
  8. Continue until all nodes at depth - 1 are processed.
  9. Return the modified tree.

Why it works: The algorithm maintains the invariant that any node at depth less than depth - 1 is untouched, and new nodes are correctly attached at the specified depth. By stopping traversal at depth - 1, no deeper nodes are unnecessarily modified.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
from typing import Optional

class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if depth == 1:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root
        
        queue = deque([(root, 1)])
        
        while queue:
            node, curr_depth = queue.popleft()
            
            if curr_depth == depth - 1:
                old_left, old_right = node.left, node.right
                node.left = TreeNode(val)
                node.right = TreeNode(val)
                node.left.left = old_left
                node.right.right = old_right
            else:
                if node.left:
                    queue.append((node.left, curr_depth + 1))
                if node.right:
                    queue.append((node.right, curr_depth + 1))
        
        return root

The implementation first handles the special case where the new row becomes the root. Otherwise, it uses a queue for level-order traversal. When reaching nodes at depth - 1, it replaces their children with new nodes while preserving existing subtrees. All other nodes are simply queued for future processing.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
    if depth == 1 {
        return &TreeNode{Val: val, Left: root}
    }
    
    queue := []*TreeNode{root}
    currDepth := 1
    
    for len(queue) > 0 {
        size := len(queue)
        if currDepth == depth-1 {
            for i := 0; i < size; i++ {
                node := queue[i]
                oldLeft := node.Left
                oldRight := node.Right
                node.Left = &TreeNode{Val: val, Left: oldLeft}
                node.Right = &TreeNode{Val: val, Right: oldRight}
            }
            break
        } else {
            for i := 0; i < size; i++ {
                node := queue[0]
                queue = queue[1:]
                if node.Left != nil {
                    queue = append(queue, node.Left)
                }
                if node.Right != nil {
                    queue = append(queue, node.Right)
                }
            }
            currDepth++
        }
    }
    
    return root
}

The Go version closely mirrors the Python logic. Differences include explicit slice handling for the queue and direct struct initialization. There is no need for a type hint system, and nil represents missing children.

Worked Examples

Example 1: root = [4,2,6,3,1,5], val = 1, depth = 2

Step Queue Action
1 [(4,1)] depth != 1, continue
2 Pop (4,1) curr_depth = 1 == depth-1 → insert new nodes 1 as left/right, attach old children
3 Queue empty return modified tree

Result: [4,1,1,2,null,null,6,3,1,5]

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

Step Queue Action
1 [(4,1)] curr_depth < depth-1 → queue children (2)
2 Pop (2,2) curr_depth = 2 == depth-1 → insert new nodes 1 as left/right, attach old children 3 and 1
3 Queue empty return modified tree

Result: [4,2,null,1,1,3,null,null,1]

Complexity Analysis

Measure Complexity Explanation
Time O(N) Each node is visited once to check depth or attach new nodes.
Space O(W) Queue stores at most the width of the tree. DFS recursion would use O(H).

The algorithm's efficiency comes from stopping traversal once we modify nodes at depth - 1, avoiding unnecessary deeper recursion.

Test Cases

# Provided examples
assert Solution().addOneRow(TreeNode(4, TreeNode(2, TreeNode(3), TreeNode(1)), TreeNode(6, TreeNode(5))), 1, 2) is not None  # depth=2
assert Solution().addOneRow(TreeNode(4, TreeNode(2, TreeNode(3), TreeNode(1))), 1, 3) is not None  # depth=3

# Edge case: add at root
assert Solution().addOneRow(TreeNode(1), 2, 1).val == 2  # new root

# Single node tree, depth=2
assert Solution().addOneRow(TreeNode(1), 3, 2).left.val == 3
assert Solution().addOneRow(TreeNode(1), 3, 2).right.val == 3

# Deep left-skewed tree
root = TreeNode(1)
cur = root
for i in range(2, 5):
    cur.left = TreeNode(i)
    cur = cur.left
assert Solution().addOneRow(root, 9, 3) is not None
Test Why
Example 1 Validates insertion at second level
Example 2 Validates insertion at third level with missing right child
Add at root Tests depth=1 edge case
Single node, depth=2