# C++ BFS & DFS sols

• BFS solution - compute average level-by-level top-down. no need to save anything globally.

``````public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> result;
queue<const TreeNode*> q1, q2;
q1.push(root);
while(!q1.empty()) {
double sum = 0, count = 0;
while(!q1.empty()) {
const TreeNode* tmp = q1.front();
q1.pop();
sum += tmp->val;
count += 1;
if(tmp->left) q2.push(tmp->left);
if(tmp->right) q2.push(tmp->right);
}
swap(q1, q2);
result.push_back(sum/count);
}
return result;
}
};
``````

DFS solution - cannot compute average (no complete info) at each level so need to keep a global memory and add to it on the fly (i.e. count and sum at each level)

``````public:
vector<double> averageOfLevels(TreeNode* root) {
vector<pair<int, double>> count_sum;
dfs(root, 0, count_sum);
vector<double> result;
for(const auto& p: count_sum)
result.push_back(p.second/p.first);
return result;
}
private:
void dfs(const TreeNode* root, int level, vector<pair<int,double>>& count_sum) {
if(!root) return;
if(level==count_sum.size()) count_sum.push_back({0, 0});
count_sum[level].first++;
count_sum[level].second+=root->val;
dfs(root->left, level+1, count_sum);
dfs(root->right, level+1, count_sum);
}
};
``````

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