# C++ BFS and DFS Solution

• DFS need to traverse the whole tree, but BFS not, so BFS solution get better performance than DFS's.

DFS solution:

``````class Solution {
public:
void dfs(TreeNode* node, int v, int d, int cur) {
if (!node) return;
if (cur == d) {
TreeNode *l = new TreeNode(v);
l->left = node->left;
node->left = l;

TreeNode *r = new TreeNode(v);
r->right = node->right;
node->right = r;
return;
}
dfs(node->left, v, d, cur + 1);
dfs(node->right, v, d, cur + 1);
}
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if (d == 1) {
TreeNode *newRoot = new TreeNode(v);
newRoot->left = root;
return newRoot;
}
dfs(root, v, d, 2);
return root;
}
};
``````

BFS 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;
}
--d;
queue<TreeNode*> q;
TreeNode *t = nullptr;
q.push(root);
while (!q.empty()) {
int size = q.size();
if (--d == 0) {
while (size--) {
t = q.front(); q.pop();
TreeNode *l = new TreeNode(v);
TreeNode *r = new TreeNode(v);
l->left = t->left; t->left = l;
r->right = t->right; t->right = r;
}
break;
}
while (size--) {
t = q.front(); q.pop();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return root;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.