Add One Row to Tree solution and explanation
Google
9 more videos on this problem
Add One Row to Tree | Made Super Easy | Google | Leetcode 623 | codestorywithMIKcodestorywithMIK · 15:08 · 13K views
Add One Row to Tree | Live Coding with Explanation | Leetcode - 623Algorithms Made Easy · 11:33 · 3K views
623. Add One Row to Tree | DFS | BFS | 2 WaysAryan Mittal · 18:00 · 2K views
ADD ONE ROW TO TREE | LEETCODE 623 | PYTHON BFS SOLUTIONCracking FAANG · 10:34 · 2K views
Leetcode - Add One Row to Tree (Python)Timothy H Chang · 4:36 · 1K views
Add One Row to Tree | LeetCode 623 | Recursion | Coders CampCoders Camp · 9:46 · 142 views
Solving LeetCode 623. Add One Row to Tree | Binary Tree | DFS | Facebook | AmazonCode Harmony · 15:50 · 98 views
LeetCode 623. Add One Row to Tree || JavaScript || BFS || Leetcode75LeetCodeWithMonu · 8:06 · 81 views
623. Add One Row to Tree | LEETCODE MEDIUM | TREE TRAVERSALcode Explainer · 7:26 · 80 views
Leetcode 623: Add One Row to TreeAlgorithms Casts · 11:37 · 75 views
The problem
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 nodecurat the depthdepth - 1, create two tree nodes with valuevalascur'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 == 1that means there is no depthdepth - 1at all, then create a tree node with valuevalas 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 <= 1051 <= depth <= the depth of tree + 1
Approach overview
Problem Overview: You are given the root of a binary tree, a value val, and a depth d. Insert a new row of nodes with value val at depth d. For every node currently at depth d-1, create two new nodes and attach the original children under them. If d = 1, the new node becomes the root and the existing tree becomes its left child.
Approach 1: Recursive Depth-First Traversal (O(n) time, O(h) space)
Use recursion to traverse the binary tree while tracking the current depth. When you reach nodes at depth d-1, create two new nodes with value val. The original left subtree becomes the left child of the new left node, and the original right subtree becomes the right child of the new right node. This works well because DFS naturally explores the structure while keeping the recursion stack limited to the tree height h. Space complexity is O(h) due to the recursion stack.
Approach 2: Iterative Breadth-First Traversal (O(n) time, O(w) space)
Perform a level-order traversal using a queue, a classic Breadth-First Search. Push the root into the queue and iterate level by level until you reach depth d-1. At that level, process each node in the queue: create two new nodes with value val, connect them as the node's new children, and reattach the original children beneath them. BFS is intuitive here because you directly move level by level, making it easy to stop exactly at the target depth.
Approach 3: Level Order BFS with Early Stop (O(n) time, O(w) space)
This variation of tree traversal uses the same queue-based level-order strategy but stops traversal once depth d-1 is reached. Instead of continuing to explore the rest of the tree, you only modify nodes in the queue at that level. This avoids unnecessary traversal and keeps the implementation clean. Space complexity is proportional to the maximum width w of the tree because the queue stores nodes from one level at a time.
Recommended for interviews: Both DFS and BFS run in O(n) time because every node may be visited once. Interviewers often prefer the BFS approach since it maps directly to the problem's “insert at depth” requirement. The recursive DFS solution demonstrates strong understanding of Depth-First Search and tree manipulation, which also makes it a solid interview answer. Showing both approaches proves you understand traversal tradeoffs.
Approach 1: Recursive Depth-First Traversal
This approach uses recursion to traverse the tree to the right depth, modifying the tree structure as necessary to add the new row of nodes. We'll use a recursive helper function that takes the current node and the current depth as parameters. If the current depth is at depth - 1, we add new nodes with the given value as left and right children. If the current depth is less, we recursively call the helper function on the left and right children (if they exist).
The base case for this recursion is reaching a null node, where we simply return.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def addOneRow(root, val, depth):
if depth == 1:
return TreeNode(val, left=root)
def dfs(node, current_depth):
if not node:
return
if current_depth == depth - 1:
node.left = TreeNode(val, left=node.left)
node.right = TreeNode(val, right=node.right)
else:
dfs(node.left, current_depth + 1)
dfs(node.right, current_depth + 1)
dfs(root, 1)
return rootThis solution defines a TreeNode class for the tree nodes and a function addOneRow which is designed to modify the tree in place. It first checks if the depth is 1, which requires creating a new root node with the provided val and making the existing tree its left subtree. For deeper levels, it recursively traverses the tree using depth-first search, adding new nodes at the correct level.
Time Complexity: O(n), because each node is visited exactly once.
Space Complexity: O(d), where d is the depth of the tree, due to the recursion stack.
Approach 2: Iterative Breadth-First Traversal
This approach uses a breadth-first search (BFS) iteration over the tree. We can use a queue to traverse the tree level by level. At each level, if the current level is depth - 1, we add a new row of nodes. Otherwise, we queue the next level of nodes.
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
TreeNode newNode = new TreeNode(val);
newNode.left = root;
return newNode;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int currentDepth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
if (currentDepth == depth - 1) {
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
TreeNode tmpLeft = node.left;
TreeNode tmpRight = node.right;
node.left = new TreeNode(val);
node.right = new TreeNode(val);
node.left.left = tmpLeft;
node.right.right = tmpRight;
}
break;
} else {
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
currentDepth++;
}
}
return root;
}
}The solution involves creating a TreeNode class and a method that adds a row to the tree. If the depth is 1, a new root node is created with the current tree as its left child. For other depths, a queue is used to perform a level-order traversal until the level before the intended depth is reached. Then, new nodes with the given value are inserted as left and right children of the current nodes. The original children are reattached to the new nodes.
Time Complexity: O(n), since every node is considered once in the BFS loop.
Space Complexity: O(n), where n is the number of nodes at the breadth of the tree, due to the queue.
Approach 3: Breadth-First Search (Level Order Traversal)
This approach involves using a queue to perform a level-order traversal of the tree. The objective is to reach nodes at depth depth-1 such that we can add new nodes with value val at the desired depth.
If the depth is 1, simply create a new root node with value val and make the original tree the left subtree of the new root.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
from collections import deque
def addOneRow(root, val, depth):
if depth == 1:
return TreeNode(val, left=root)
queue = deque([root])
current_depth = 1
while queue:
current_level_size = len(queue)
if current_depth == depth - 1:
for _ in range(current_level_size):
node = queue.popleft()
node.left = TreeNode(val, left=node.left)
node.right = TreeNode(val, right=node.right)
return root
for _ in range(current_level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
current_depth += 1
return rootpublic class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
import java.util.LinkedList;
public class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
return new TreeNode(val, root, null);
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
int currentDepth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
if (currentDepth == depth - 1) {
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
node.left = new TreeNode(val, node.left, null);
node.right = new TreeNode(val, null, node.right);
}
return root;
}
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
currentDepth++;
}
return root;
}
}In this Python solution, a queue is used for breadth-first search (BFS) traversal. When the current depth equals depth-1, new nodes are inserted between the current nodes and their children, effectively at the specified depth. If the depth is 1, a new root is created with the existing root as its left child.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(n) in the worst case to keep the queue, if the tree is a balanced tree, or O(h) where h is the height of the tree in a skewed tree.
Approach 4: Depth-First Search (Recursive)
This approach uses a recursive depth-first search to traverse the tree. The function is designed to target depth depth-1 to manipulate and add the new nodes at the desired level.
An edge case at depth 1 involves creating a new root, similar to the BFS approach.
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if (depth == 1) {
return new TreeNode(val, root, nullptr);
}
dfs(root, val, depth, 1);
return root;
}
void dfs(TreeNode* node, int val, int depth, int currentDepth) {
if (!node) return;
if (currentDepth == depth - 1) {
node->left = new TreeNode(val, node->left, nullptr);
node->right = new TreeNode(val, nullptr, node->right);
return;
}
dfs(node->left, val, depth, currentDepth + 1);
dfs(node->right, val, depth, currentDepth + 1);
}
};public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode AddOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
return new TreeNode(val, root);
}
AddOneRowDFS(root, val, depth, 1);
return root;
}
private void AddOneRowDFS(TreeNode node, int val, int targetDepth, int currentDepth) {
if (node == null) return;
if (currentDepth == targetDepth - 1) {
node.left = new TreeNode(val, node.left, null);
node.right = new TreeNode(val, null, node.right);
return;
}
AddOneRowDFS(node.left, val, targetDepth, currentDepth + 1);
AddOneRowDFS(node.right, val, targetDepth, currentDepth + 1);
}
}The C++ solution employs recursion to explore each depth level. The recursion continues to descend until reaching depth-1, where new nodes are created and attached. The solution gracefully handles the edge case of depth being 1 by creating a new root node.
Time Complexity: O(n), where n is the total number of nodes in the tree, as each node is visited once.
Space Complexity: O(h) due to the recursive call stack, where h is the height of the tree.
Approach 5: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function addOneRow(root: TreeNode | null, val: number, depth: number): TreeNode | null {
function dfs(root, d) {
if (!root) {
return;
}
if (d == depth - 1) {
root.left = new TreeNode(val, root.left, null);
root.right = new TreeNode(val, null, root.right);
return;
}
dfs(root.left, d + 1);
dfs(root.right, d + 1);
}
if (depth == 1) {
return new TreeNode(val, root);
}
dfs(root, 1);
return root;
}/**
* 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}
}
var dfs func(root *TreeNode, d int)
dfs = func(root *TreeNode, d int) {
if root == nil {
return
}
if d == depth-1 {
l, r := &TreeNode{Val: val, Left: root.Left}, &TreeNode{Val: val, Right: root.Right}
root.Left, root.Right = l, r
return
}
dfs(root.Left, d+1)
dfs(root.Right, d+1)
}
dfs(root, 1)
return root
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Traversal | Time Complexity: O(n), because each node is visited exactly once. |
| Iterative Breadth-First Traversal | Time Complexity: O(n), since every node is considered once in the BFS loop. |
| Breadth-First Search (Level Order Traversal) | Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once. Space Complexity: O(n) in the worst case to keep the queue, if the tree is a balanced tree, or O(h) where h is the height of the tree in a skewed tree. |
| Depth-First Search (Recursive) | Time Complexity: O(n), where n is the total number of nodes in the tree, as each node is visited once. Space Complexity: O(h) due to the recursive call stack, where h is the height of the tree. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Traversal | O(n) | O(h) | When recursion is preferred and tree height is manageable |
| Iterative Breadth-First Traversal | O(n) | O(w) | Best when you want direct control over levels in the tree |
| Level Order BFS with Early Stop | O(n) | O(w) | Clean solution when modifying nodes only at a specific depth |
Frequently asked questions
Is Add One Row to Tree easy or hard?
Add One Row to Tree is considered a Medium difficulty problem on LeetCode. The main challenge is correctly handling tree traversal and pointer reassignment when inserting the new nodes while preserving the existing subtrees.
Add One Row to Tree Python/Java solution
Python implementations often use recursive DFS to track depth and insert nodes when depth == d-1. Java solutions commonly use a queue for BFS level-order traversal to reach the correct level and modify children. Both implementations run in O(n) time.
How to solve Add One Row to Tree in O(n)?
Traverse the tree until reaching depth d-1 using either DFS or BFS. For each node at that level, create two new nodes with value val and attach the original left and right subtrees beneath them. Each node is processed at most once, resulting in O(n) time complexity.
What is the best approach for Add One Row to Tree?
The Breadth-First Search (level order traversal) approach is typically the most straightforward. You traverse the tree level by level using a queue until reaching depth d-1, then insert new nodes under each node at that level. This approach runs in O(n) time and uses O(w) space where w is the maximum width of the tree.
Is Add One Row to Tree asked at Google/Amazon/Meta?
Binary tree modification problems like Add One Row to Tree frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants often test traversal techniques, tree restructuring, and understanding of DFS or BFS patterns.
What data structure is used in Add One Row to Tree?
The primary data structure is a binary tree. Solutions typically use recursion with a call stack for Depth-First Search or a queue for Breadth-First Search to traverse levels and insert the new nodes at the correct depth.
What is the time complexity of Add One Row to Tree?
The time complexity is O(n) because every node in the binary tree may need to be visited once to reach the target depth. Both DFS and BFS implementations achieve this complexity. Space complexity is O(h) for recursive DFS (tree height) or O(w) for BFS (maximum level width).