algoadvance

Leetcode 623. Add One Row to Tree

Problem Statement

You are given the root of a binary tree and two integers val and depth. You need to add a row of nodes with value val at the given depth depth.

More specifically, the given depth depth is 1 means the row should be added at the root, and the tree nodes connected to the root should be moved down by one level.

Clarifying Questions

  1. What should we do if the tree is empty (root is nullptr)?
    • If the tree is empty, we just need to create a new node with the given val.
  2. What are the constraints on val and depth?
    • Typically, constraints would be such that val is an integer (INT_MIN <= val <= INT_MAX), and depth is a positive integer.
  3. Are there any constraints on the initial depth of the tree?
    • No specific constraint, but typical constraints might apply depending on the problem’s expected input size.
  4. What is the expected structure of the tree nodes?
    • Each tree node is defined as: 
      struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

Strategy

To add a new row at a specific depth:

  1. If the desired depth is 1, we create a new root node with value val and set the current tree as its left child.
  2. To insert the new row at depth depth, we perform a level-order traversal (BFS), stopping at level depth - 1. For each node at this level, we insert new nodes with value val as their left and right children, preserving the original children of these nodes.

Code

#include <queue>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr, right(nullptr))) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        // Case when depth is 1
        if(depth == 1) {
            TreeNode* newRoot = new TreeNode(val);
            newRoot->left = root;
            return newRoot;
        }

        // Level order traversal (BFS) to find the nodes at depth - 1
        std::queue<TreeNode*> queue;
        queue.push(root);
        int currentDepth = 1;

        // Continue until we reach depth - 1
        while(currentDepth < depth - 1) {
            int size = queue.size();
            for(int i = 0; i < size; ++i) {
                TreeNode* node = queue.front();
                queue.pop();
                if(node->left) queue.push(node->left);
                if(node->right) queue.push(node->right);
            }
            ++currentDepth;
        }

        // Insert new row
        while(!queue.empty()) {
            TreeNode* node = queue.front();
            queue.pop();
            TreeNode* oldLeft = node->left;
            TreeNode* oldRight = node->right;
            node->left = new TreeNode(val);
            node->left->left = oldLeft;
            node->right = new TreeNode(val);
            node->right->right = oldRight;
        }

        return root;
    }
};

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of nodes in the tree. This is because we need to perform a level-order traversal which visits each node exactly once. The space complexity is also O(n) due to the queue used for BFS traversal.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI