Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Move from brute-force thinking to an efficient approach using tree strategy.
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:
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.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:
[1, 104].[1, 104].-100 <= Node.val <= 100-105 <= val <= 1051 <= depth <= the depth of tree + 1Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[4,2,6,3,1,5] 1 2
[4,2,null,3,1] 1 3
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #623: Add One Row to Tree
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
private int val;
private int depth;
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
return new TreeNode(val, root, null);
}
this.val = val;
this.depth = depth;
dfs(root, 1);
return root;
}
private void dfs(TreeNode root, int d) {
if (root == null) {
return;
}
if (d == depth - 1) {
TreeNode l = new TreeNode(val, root.left, null);
TreeNode r = new TreeNode(val, null, root.right);
root.left = l;
root.right = r;
return;
}
dfs(root.left, d + 1);
dfs(root.right, d + 1);
}
}
// Accepted solution for LeetCode #623: Add One Row to Tree
/**
* 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
}
# Accepted solution for LeetCode #623: Add One Row to Tree
# 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
class Solution:
def addOneRow(
self, root: Optional[TreeNode], val: int, depth: int
) -> Optional[TreeNode]:
def dfs(root, d):
if root is None:
return
if d == depth - 1:
root.left = TreeNode(val, root.left, None)
root.right = TreeNode(val, None, root.right)
return
dfs(root.left, d + 1)
dfs(root.right, d + 1)
if depth == 1:
return TreeNode(val, root)
dfs(root, 1)
return root
// Accepted solution for LeetCode #623: Add One Row to Tree
struct Solution;
use rustgym_util::*;
trait Postorder {
fn postorder(self, depth: i32, v: i32, d: i32) -> TreeLink;
}
impl Postorder for TreeLink {
fn postorder(self, depth: i32, v: i32, d: i32) -> TreeLink {
if let Some(node) = self {
let mut node = node.borrow_mut();
let val = node.val;
let left = node.left.take();
let right = node.right.take();
let mut left = left.postorder(depth + 1, v, d);
let mut right = right.postorder(depth + 1, v, d);
if depth + 1 == d {
left = tree!(v, left, None);
right = tree!(v, None, right);
}
tree!(val, left, right)
} else {
None
}
}
}
impl Solution {
fn add_one_row(root: TreeLink, v: i32, d: i32) -> TreeLink {
if d == 1 {
tree!(v, root, None)
} else {
root.postorder(1, v, d)
}
}
}
#[test]
fn test() {
let root = tree!(4, tree!(2, tree!(3), tree!(1)), tree!(6, tree!(5), None));
let v = 1;
let d = 2;
let res = tree!(
4,
tree!(1, tree!(2, tree!(3), tree!(1)), None),
tree!(1, None, tree!(6, tree!(5), None))
);
assert_eq!(Solution::add_one_row(root, v, d), res);
let root = tree!(4, tree!(2, tree!(3), tree!(1)), None);
let v = 1;
let d = 3;
let res = tree!(
4,
tree!(2, tree!(1, tree!(3), None), tree!(1, None, tree!(1))),
None
);
assert_eq!(Solution::add_one_row(root, v, d), res);
}
// Accepted solution for LeetCode #623: Add One Row to Tree
/**
* 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;
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.