# Two Clean C++ Solutions: BFS and DFS

• ``````///BFS, O(n) Space, O(n) Time, longer to write tho
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
queue<pair<TreeNode *, list<vector<int>>::iterator>> q;
vector<vector<int>> result;
if (root == nullptr)
return result;
list<vector<int>> buffer;
buffer.emplace_back();
q.emplace(root, buffer.begin());
while (q.size())
{
auto cur = q.front();q.pop();
auto iter = cur.second;
auto node = cur.first;
iter->push_back(node->val);
if (node->left)
{
if(iter == buffer.begin())
buffer.emplace_front();
q.emplace(node->left, prev(iter));
}
if (node->right)
{
if(next(iter) == buffer.end())
buffer.emplace_back();
q.emplace(node->right, next(iter));
}
}
copy(buffer.begin(), buffer.end(), back_inserter(result));
return result;
}
};
/// DFS, O(n) Sapce and O(nlgn) Time, a little bit slower but easier to write.
class Solution {
map<int, map<int, vector<int>>> table;
void dfs(TreeNode * root, int i, int j)
{
if (root == nullptr)
return;
table[j][i].push_back(root->val);
dfs(root->left, i + 1, j - 1);
dfs(root->right, i + 1, j + 1);
}
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
dfs(root, 0, 0);
vector<vector<int>> result;
for (const auto & col : table)
{
result.emplace_back();
for (const auto & elem : col.second)
{
const auto & vec = elem.second;
copy(vec.begin(), vec.end(), back_inserter(result.back()));
}
}
return result;
}
};``````

• @fentoyal Great DFS solution! Sharing some thinkings on when to use BFS or DFS

• If the tree is balanced, use DFS or BFS

• If not balanced, use BFS, because DFS use bigger stack, and preallocated 2D matrix will have many entries empty (I am not talking about your solution, I am talking about others' solution).

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