Add One Row to Tree Solution in Java

Problem Description

So, you’ve got a tree, right? Not the kind you find in your backyard, but a binary tree. Now, imagine you want to add a new row of nodes at a specific depth. Sounds simple, right? Well, it’s like trying to add a new branch to a tree that’s already grown tall and proud. You can’t just slap a branch on there; you need to do it delicately, or you might just ruin the whole thing!

In this problem, you’re tasked with adding a new row of nodes with a given value v at a specified depth d. If d is 1, you’re basically creating a new root and making the old root the left child. If d is greater than 1, you need to traverse the tree to find the right spot to insert your new nodes. It’s like trying to find the perfect spot for a new plant in your garden without disturbing the existing ones.

Code Solution

class Solution {
  public TreeNode addOneRow(TreeNode root, int v, int d) {
    if (d == 1) {
      TreeNode newRoot = new TreeNode(v);
      newRoot.left = root;
      return newRoot;
    }

    int depth = 0;
    Queue q = new ArrayDeque<>(List.of(root));

    while (!q.isEmpty()) {
      ++depth;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode node = q.poll();
        if (node.left != null)
          q.offer(node.left);
        if (node.right != null)
          q.offer(node.right);
        if (depth == d - 1) {
          TreeNode cachedLeft = node.left;
          TreeNode cachedRight = node.right;
          node.left = new TreeNode(v);
          node.right = new TreeNode(v);
          node.left.left = cachedLeft;
          node.right.right = cachedRight;
        }
      }
      if (depth == d - 1)
        break;
    }

    return root;
  }
}
    

Approach

The approach here is straightforward yet elegant. If the depth d is 1, you create a new root node and attach the existing tree as its left child. For depths greater than 1, you traverse the tree level by level using a queue until you reach the level just before the desired depth. At that level, you create new nodes with the value v and attach the existing children to these new nodes. It’s like carefully placing new plants in your garden without uprooting the old ones!

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we may need to traverse all nodes.

Space Complexity: O(W), where W is the maximum width of the tree. This is due to the queue used for level-order traversal.

Real-World Example

Imagine you’re a gardener who wants to add a new row of flowers to your garden. You can’t just throw them in anywhere; you need to find the right spot that complements the existing flowers. Similarly, in this problem, you’re adding a new row of nodes to a binary tree, ensuring that the structure remains intact and beautiful.