Add One Row to Tree – C++ Solution

Problem Description

So, you want to add a row to a tree? Sounds simple, right? Well, welcome to the world of binary trees, where things can get as twisted as your last family reunion! The problem is to add 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. If d is greater than 1, you’re just adding nodes at the specified level, like adding a new layer of frosting on a cake that’s already too sweet.

Imagine you have a family tree, and you want to add a new generation. You can’t just slap them on top; you have to find the right spot!

Code Solution

Copy Code

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{{root}};

    while (!q.empty()) {
      ++depth;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode* node = q.front();
        q.pop();
        if (node->left)
          q.push(node->left);
        if (node->right)
          q.push(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 clever. We use a breadth-first search (BFS) to traverse the tree level by level. When we reach the level just before the desired depth d, we create new nodes with the value v and attach the existing children to these new nodes. It’s like adding a new layer to a cake without disturbing the existing layers—just a little more frosting!

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. We may need to visit every node in the worst case.

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

Real-World Example

Think of a tree as a family tree. You have grandparents, parents, and children. Now, if you want to add a new generation (like your kids), you can’t just throw them on top of the grandparents. You need to find the right spot in the family hierarchy. This problem is just like that—adding a new row of nodes at the right depth in a binary tree!