Add One Row to Tree

Medium
1924.

Add One Row to Tree

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.

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 cur at depth depth - 1, create two new nodes holding value: one becomes cur'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 holding value, 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^5
  • 1 <= depth <= the depth of the tree + 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} value
 * @param {number} depth
 * @return {TreeNode}
 */
var addOneRow = function(root, value, depth) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 cur at depth depth - 1, create two new nodes holding value: one becomes cur'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 holding value, 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^5
  • 1 <= depth <= the depth of the tree + 1

Hints for Add One Row to Tree

  1. Hint 1

    Only the nodes at depth depth - 1 change; everything else stays exactly where it is.

  2. Hint 2

    Walk down the tree carrying the current depth (DFS) or row by row (BFS) until you reach depth depth - 1.

  3. 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 == 1 separately.

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

  1. If depth == 1, return a new node holding value whose left child is root.
  2. Otherwise run a DFS carrying the depth d of the current node, starting at d = 1.
  3. When d == depth - 1, set node.left = new Node(value, left = old left) and node.right = new Node(value, right = old right), and stop descending.
  4. 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 - 1 with 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 root

Java

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)