LeetCode 623: Add One Row to Tree Solution in Python – A Step-by-Step Guide

Imagine you’re a tree architect tasked with enhancing a binary tree—say, a family tree or a company org chart—by adding a new row of nodes with a specific value, like a new generation, at a given depth. You need to slot these nodes in just right, connecting them to the existing structure. That’s the challenge of LeetCode 623: Add One Row to Tree, a medium-level problem that’s all about modifying a binary tree at a specific level. Using Python, we’ll explore two solutions: the Best Solution, a recursive depth-first search (DFS) with level tracking for elegance, and an Alternative Solution, an iterative breadth-first search (BFS) with a queue for a level-by-level approach. With detailed examples, beginner-friendly breakdowns—especially for the recursive method—and clear code, this guide will help you grow that tree, whether you’re new to coding or leveling up. Let’s grab our pruning tools and start adding!

What Is LeetCode 623: Add One Row to Tree?

In LeetCode 623: Add One Row to Tree, you’re given a binary tree (root node with val, left, and right attributes), an integer val (the value for new nodes), and an integer depth (where to add the row, 1-based). Your task is to add a row of nodes with value val at depth d, connecting them as left and right children of nodes at depth d-1, shifting the original subtrees down. For example, adding val=1 at depth=2 to a tree [4,2,6] transforms it into [4,1,1,2,null,null,6]. This problem tests your ability to traverse and modify a tree at a specific level.

Problem Statement

Input:

root: Root of a binary tree.
val: Integer value for new nodes.
depth: Integer depth to add row (1 ≤ depth ≤ tree height + 1).

Output: Root of the modified binary tree.
Rules:

Add nodes with val at depth d.
Original left/right subtrees become left/right children of new nodes.
Depth is 1-based (root = 1).

Constraints

Number of nodes: 1 to 10⁴.
-100 ≤ Node.val ≤ 100.
-10⁵ ≤ val ≤ 10⁵.
1 ≤ depth ≤ 10.

Examples

Input:

root = [4,2,6,3,1,5], val = 1, depth = 2
Tree: 4->2(left), 4->6(right), 2->3(left), 2->1(right), 6->5(left).
Output: [4,1,1,2,null,null,6,3,1,5]

Add 1s at depth 2, 2 and 6 shift down.

Input:

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

Input:

root = [1], val = 5, depth = 1
Output: [5,1]

These examples show the transformation—let’s solve it!

Understanding the Problem: Adding a Tree Row

To solve LeetCode 623: Add One Row to Tree in Python, we need to traverse a binary tree to depth d-1, insert new nodes with value val as children of those nodes, and reattach the original subtrees. A naive approach might rebuild the tree, but we can modify it in place. We’ll use:

Best Solution (Recursive DFS with Level Tracking): O(n) time, O(h) space—n is nodes, h is height—elegant and recursive.
Alternative Solution (Iterative BFS with Queue): O(n) time, O(w) space—w is max width—level-based and explicit.

Let’s start with the recursive solution, breaking it down for beginners.

Best Solution: Recursive DFS with Level Tracking

Why This Is the Best Solution

The recursive DFS with level tracking is the top choice for LeetCode 623 because it’s efficient—O(n) time to visit each node—and leverages the tree’s recursive nature, making it concise and intuitive. It uses O(h) space for the call stack (h ≤ 10), fitting constraints perfectly. It’s like climbing the tree to the right level and adding branches!

How It Works

Think of this as growing a tree layer:

Step 1: Base Case:

If root is None, return None.

Step 2: Check Depth:

If current depth = d-1, add new nodes.
New left: val, its left = old left.
New right: val, its right = old right.

Step 3: Recurse:

If not at d-1, recurse on left and right with depth + 1.

Step 4: Return Root:

Return modified root.

It’s like a tree surgeon—add at the right depth!

Step-by-Step Example

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

Initial: [4,2,6] (4->2(left), 4->6(right)).
DFS (depth=1):

Not 1 (d-1), recurse.
Left (2, depth=2):

Depth = 1, add nodes.
New left: 1, 1.left = 2, 2.left/right = None/null.
New right: 1, 1.right = None.

Right (6, depth=2):

New left: 1, 1.left = 6.
New right: 1, 1.right = None.

Result: [4,1,1,2,null,null,6].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:
        # Step 1: Special case for depth = 1
        if depth == 1:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root

        # Step 2: Recursive helper function
        def dfs(node, curr_depth):
            if not node:
                return

            # Step 3: Add row at depth d-1
            if curr_depth == depth - 1:
                # Add new left node
                old_left = node.left
                node.left = TreeNode(val)
                node.left.left = old_left
                # Add new right node
                old_right = node.right
                node.right = TreeNode(val)
                node.right.right = old_right
            else:
                # Recurse deeper
                dfs(node.left, curr_depth + 1)
                dfs(node.right, curr_depth + 1)

        # Step 4: Start DFS from root
        dfs(root, 1)
        return root

Lines 1-5: TreeNode class (standard).
Lines 10-13: Handle depth=1:

New root with val, old root as left child.

Lines 16-30: DFS helper:

Base case: null node.
At d-1: Add new nodes, reattach subtrees.
Else: Recurse with increased depth.

Line 33: Start DFS at depth 1.
Time Complexity: O(n)—visit each node once.
Space Complexity: O(h)—recursion stack.

This is like a tree grower—elegant and precise!

Alternative Solution: Iterative BFS with Queue

Why an Alternative Approach?

The iterative BFS approach uses a queue to process the tree level-by-level—O(n) time, O(w) space (w = max width). It’s more explicit, finding the target depth directly, but uses more space (w ≤ 10⁴/2). It’s like scanning the tree floor-by-floor!

How It Works

Picture this as a level sweep:

Step 1: Handle depth=1 separately.
Step 2: BFS to depth d-1:

Use queue to track nodes and levels.

Step 3: Add row at d-1:

For each node, insert new children, reattach subtrees.

Step 4: Return root.

It’s like a tree level editor—scan and add!

Step-by-Step Example

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

Init: Queue = [(4, 1)].
Level 1: Pop (4, 1):

Depth = 1 = 2-1, process.
Left: 2 → new left = 1, 1.left = 2.
Right: 6 → new right = 1, 1.right = 6.

Result: [4,1,1,2,null,null,6].

Code for BFS Approach

from collections import deque

class Solution:
    def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:
        # Step 1: Handle depth = 1
        if depth == 1:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root

        # Step 2: BFS to find depth d-1
        queue = deque([(root, 1)])
        while queue:
            node, curr_depth = queue.popleft()

            # Step 3: Add row at depth d-1
            if curr_depth == depth - 1:
                # Process all nodes at this level
                for node, _ in list(queue) + [(node, curr_depth)]:
                    old_left = node.left
                    node.left = TreeNode(val)
                    node.left.left = old_left

                    old_right = node.right
                    node.right = TreeNode(val)
                    node.right.right = old_right
                break

            # Add children to queue
            if node.left:
                queue.append((node.left, curr_depth + 1))
            if node.right:
                queue.append((node.right, curr_depth + 1))

        # Step 4: Return root
        return root

Lines 10-13: Depth=1 case.
Lines 16-31: BFS:

Queue tracks node and depth.
At d-1, add new nodes for all in level.
Else, enqueue children.

Time Complexity: O(n)—visit each node.
Space Complexity: O(w)—queue size.

It’s a level-by-level tree mod—clear but bulkier!

Comparing the Two Solutions

Recursive DFS (Best):

Pros: O(n) time, O(h) space, concise and natural.
Cons: Recursion depth for tall trees.

Iterative BFS (Alternative):

Pros: O(n) time, O(w) space, explicit level control.
Cons: More space, complex logic.

DFS wins for elegance.

Additional Examples and Edge Cases

Input: root = [1], val = 2, depth = 2

Output: [1,2,2].

Input: root = [], val = 1, depth = 1

Output: [1].

Both handle these well.

Complexity Breakdown

DFS: Time O(n), Space O(h).
BFS: Time O(n), Space O(w).

DFS is leaner.

Key Takeaways

DFS: Recursive depth—smart!
BFS: Level sweep—clear!
Trees: Modifying is fun.
Python Tip: Recursion rocks—see Python Basics.

Final Thoughts: Grow That Tree

LeetCode 623: Add One Row to Tree in Python is a fun tree-modification challenge. Recursive DFS offers simplicity and efficiency, while iterative BFS provides level control. Want more? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 617: Merge Two Binary Trees. Ready to expand? Head to Solve LeetCode 623 on LeetCode and add that row today!