5. Level Order (BFS)

// Queue
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (!root) return ans;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        while (sz--) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
        ans.push_back(level);
    }
    return ans;
}

// DFS Recursive
class Solution {
    void dfs(TreeNode* root, int level,
             vector<vector<int>>& ans) {
        if (!root)
            return;
        if (level == ans.size())
            ans.push_back({});
        ans[level].push_back(root->val);
        dfs(root->left, level + 1, ans);
        dfs(root->right, level + 1, ans);
    }

public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, 0, ans);
        return ans;
    }
};

Applications

1. Traversing a Tree from Top to Bottom.
2. Care about depth, distance and levels.
3. Looking for a closest match/closest node to root.