Add One Row to Tree — Solution in Python, Java & C++
Add One Row to Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Add One Row to Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree and two integers value and depth, insert a new row of nodes holding value at the given depth (the root is at depth 1) and return the root.
- For every node
curat depthdepth - 1, create two new nodes holdingvalue: one becomescur's new left child and the other its new right child. cur's original left subtree becomes the left subtree of the new left node, and its original right subtree becomes the right subtree of the new right node.- If
depth == 1, there is no depth 0: create a single new root holdingvalue, with the whole original tree as its left subtree.
Example 1
Input: root = [4,2,6,3,1,5], value = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
Explanation: Both children of the root get a new parent holding 1: the old left subtree hangs to the left of the new left node, the old right subtree to the right of the new right node.
Example 2
Input: root = [4,2,null,3,1], value = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]
Explanation: Only node 2 is at depth 2, so it alone gets two new children; 3 moves under the new left node and 1 under the new right node.
Example 3
Input: root = [5], value = 7, depth = 1
Output: [7,5]
Explanation: With depth 1 the new node becomes the root, and the whole old tree becomes its left subtree.
Constraints
The number of nodes in the tree is in the range [1, 10^4]The depth of the tree is in the range [1, 10^4]-100 <= Node.val <= 100-10^5 <= value <= 10^51 <= depth <= the depth of the tree + 1
Hints for Add One Row to Tree
Hint 1
Only the nodes at depth
depth - 1change; everything else stays exactly where it is.Hint 2
Walk down the tree carrying the current depth (DFS) or row by row (BFS) until you reach depth
depth - 1.Hint 3
At such a node, the new left node adopts the old left child as its left child and the new right node adopts the old right child as its right child. Handle
depth == 1separately.
How to solve Add One Row to Tree
The new row sits between the nodes at depth depth - 1 and their children, so the only work is to find those nodes and splice two new nodes under each. Depth 1 is the special case where a new root is placed above everything.
Approach
- If
depth == 1, return a new node holdingvaluewhose left child isroot. - Otherwise run a DFS carrying the depth
dof the current node, starting atd = 1. - When
d == depth - 1, setnode.left = new Node(value, left = old left)andnode.right = new Node(value, right = old right), and stop descending. - Otherwise recurse into both children with
d + 1. Return the root.
Why it works
Every node at depth depth - 1 is reached exactly once and gets the two new nodes, so the new nodes form exactly the row at depth depth. Old subtrees are reattached on the side the statement fixes, so nothing else moves.
Complexity
- Time —
O(n) at worst — only the nodes above the new row are visited - Space —
O(h) for the recursion
Pitfalls
- The old left subtree goes under the new left node's left, the old right subtree under the new right node's right — not the other way round.
- Stop at depth
depth - 1; recursing further would also visit the newly added nodes. - A node at depth
depth - 1with no children still gets both new nodes.
Reference solution
Python
from typing import Optional
def addOneRow(root: Optional[TreeNode], value: int, depth: int) -> Optional[TreeNode]:
if depth == 1:
return TreeNode(value, root, None)
level = [root]
for _ in range(depth - 2):
nxt = []
for node in level:
if node.left is not None:
nxt.append(node.left)
if node.right is not None:
nxt.append(node.right)
level = nxt
for node in level:
node.left = TreeNode(value, node.left, None)
node.right = TreeNode(value, None, node.right)
return rootJava
public static TreeNode addOneRow(TreeNode root, int value, int depth) {
if (depth == 1) return new TreeNode(value, root, null);
insertRow(root, value, depth, 1);
return root;
}
static void insertRow(TreeNode node, int value, int depth, int d) {
if (node == null) return;
if (d == depth - 1) {
node.left = new TreeNode(value, node.left, null);
node.right = new TreeNode(value, null, node.right);
return;
}
insertRow(node.left, value, depth, d + 1);
insertRow(node.right, value, depth, d + 1);
}C++
void insertRow(TreeNode* node, int value, int depth, int d);
TreeNode* addOneRow(TreeNode* root, int value, int depth) {
if (depth == 1) return new TreeNode(value, root, nullptr);
insertRow(root, value, depth, 1);
return root;
}
void insertRow(TreeNode* node, int value, int depth, int d) {
if (!node) return;
if (d == depth - 1) {
node->left = new TreeNode(value, node->left, nullptr);
node->right = new TreeNode(value, nullptr, node->right);
return;
}
insertRow(node->left, value, depth, d + 1);
insertRow(node->right, value, depth, d + 1);
}JavaScript
var addOneRow = function(root, value, depth) {
if (depth === 1) return new TreeNode(value, root, null);
var level = [root];
for (var d = 1; d < depth - 1; d++) {
var next = [];
for (var i = 0; i < level.length; i++) {
if (level[i].left !== null) next.push(level[i].left);
if (level[i].right !== null) next.push(level[i].right);
}
level = next;
}
for (var j = 0; j < level.length; j++) {
var node = level[j];
node.left = new TreeNode(value, node.left, null);
node.right = new TreeNode(value, null, node.right);
}
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)