- DFS to find the element 1-above our depth
- BFS to move across the level
- if curr has a left child
- create a TreeNode as curs left child, make its left child the previous left child
- if curr has a right child
- create a TReeNode as curs right child, make its right child the previous right child
🤔What Did I Struggle With?
- solution was correct, took me a little while to come to it
- was uncertain of combining traversal methods
- using just BFS was enough
💡 Explanation of Solution
- use a queue to perform level-order traversal (BFS)
- continue traversal until we reach depth-1
⌛ Complexity Analysis
- Worst case of O(n)
💻 Implementation of Solution
class Solution {public: TreeNode* addOneRow(TreeNode* root, int val, int depth) { if(root == nullptr) return nullptr; if(depth == 1) { TreeNode* newRoot = new TreeNode(val); newRoot->left = root; return newRoot; } queue<TreeNode*> q; q.push(root); int currentDepth = 1; while(!q.empty()) { int levelSize = q.size(); if(currentDepth == depth - 1) { //modify the nodes at the current depth for(int i=0; i < levelSize; i++) { TreeNode* node = q.front(); q.pop(); TreeNode* oldLeft = node->left; TreeNode* oldRight = node->right; node->left = new TreeNode(val); node->right = new TreeNode(val); node->left->left = oldLeft; node->right->right = oldRight; } break; } // Continue BFS for (int i = 0; i < levelSize; ++i) { TreeNode* node = q.front(); q.pop(); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } ++currentDepth; } return root; }};