Add One Row to Tree

Add One Row to Tree

What is this problem about?

The Add One Row to Tree coding problem asks you to insert a full row of nodes with a specific value at a given depth d in a binary tree. For every existing node at depth d-1, you create two new nodes. The old left child becomes the left child of the new left node, and the old right child becomes the right child of the new right node.

Why is this asked in interviews?

This is a standard Tree traversal question used by Microsoft and Google. it tests your ability to manipulate pointers and maintain tree structure while navigating to a specific level. It requires precision in handling child assignments to prevent losing entire subtrees.

Algorithmic pattern used

This can be solved using either the Breadth-First Search (BFS) or Depth-First Search (DFS) interview pattern.

• BFS: Traverse level by level until you reach depth d-1.
• DFS: Use recursion to go down the tree, keeping track of the current depth.

Example explanation

Target depth: 2, Value: 1. Original tree:

    4
   / \
  2   6

At depth 1 (node 4), we add the new row:

      4
     / \
    1   1
   /     \
  2       6

The original 2 is now the left child of the new 1, and the original 6 is the right child of the other new 1.

Common mistakes candidates make

• Depth 1 Edge Case: If the depth is 1, the original root becomes the left child of a brand-new root. This case is often forgotten.
• Losing Subtrees: Incorrectly reassigning pointers so that the original children of the d-1 nodes are deleted or orphaned.
• Off-by-one errors: Navigating to depth d instead of depth d-1 to perform the insertion.

Interview preparation tip

In tree problems involving "rows" or "levels," BFS is often more intuitive. However, DFS is usually more concise to code. Practice both to see which one you can implement faster without bugs.