Add One Row to Tree

MediumTreesbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree and integers val and depth, insert a new row of nodes with value val at depth depth (the root is at depth 1). Return the root of the modified tree. For every existing node cur at depth depth - 1, create two new nodes with value val. The new node becomes cur's new left child and takes cur's old left subtree as **its left** subtree; the other new node becomes cur's new right child and takes cur's old right subtree as **its right** subtree. Both new nodes are created even when the old child was missing. If depth == 1, create a new root with value val whose left child is the original tree.

Examples

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
Two nodes with value 1 are placed under the root; 2 hangs left of the new left node and 6 hangs right of the new right node.
Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]
Node 2 is the only node at depth 2, so it receives the new row.

Constraints

  • 1 <= number of nodes <= 10^4
  • -100 <= Node.val <= 100
  • -10^5 <= val <= 10^5
  • 1 <= depth <= (height of the tree) + 1

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems