Tree BFS Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Level order: snapshot the queue size, pop exactly that many → one level.
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    if (!root) return levels;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();                      // nodes on this level, fixed before we push children
        vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);   // children belong to the next round
            if (node->right) q.push(node->right);
        }
        levels.push_back(level);
    }
    return levels;
}

// Per-level answers: the same rounds, but fold each level into one value.
// Here: the right side view (last node of each round) and the largest value per row.
vector<int> rightSideView(TreeNode* root) {
    vector<int> view;
    if (!root) return view;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == size - 1) view.push_back(node->val);   // last in its round = seen from the right
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return view;
}

vector<int> largestValues(TreeNode* root) {
    vector<int> best;
    if (!root) return best;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        int mx = q.front()->val;                    // start from a real value, never 0
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            mx = max(mx, node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        best.push_back(mx);
    }
    return best;
}

// Distance from a start node in every direction: add parent links, then BFS like a graph.
// Returns the values of all nodes exactly k edges away from start.
vector<int> nodesAtDistance(TreeNode* root, TreeNode* start, int k) {
    unordered_map<TreeNode*, TreeNode*> parent;
    function<void(TreeNode*)> link = [&](TreeNode* node) {
        for (TreeNode* child : {node->left, node->right})
            if (child) { parent[child] = node; link(child); }
    };
    if (root) link(root);

    queue<TreeNode*> q;
    unordered_set<TreeNode*> seen{start};       // without this we walk straight back where we came from
    q.push(start);
    for (int dist = 0; !q.empty(); dist++) {
        if (dist == k) {                         // everything in the queue is exactly k away
            vector<int> out;
            while (!q.empty()) { out.push_back(q.front()->val); q.pop(); }
            return out;
        }
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            TreeNode* up = parent.count(node) ? parent[node] : nullptr;
            for (TreeNode* nb : {node->left, node->right, up})
                if (nb && seen.insert(nb).second) q.push(nb);
        }
    }
    return {};
}

// Next pointers in O(1) space: walk the current level through its `next` links
// while building the level below with a dummy head. Works for any shape of tree.
// struct Node { int val; Node *left, *right, *next; };   (given by LeetCode)
Node* connect(Node* root) {
    Node* levelStart = root;
    while (levelStart) {
        Node dummy(0);                            // dummy.next will be the first node of the level below
        Node* tail = &dummy;
        for (Node* cur = levelStart; cur; cur = cur->next) {   // this level is already linked
            if (cur->left)  { tail->next = cur->left;  tail = tail->next; }
            if (cur->right) { tail->next = cur->right; tail = tail->next; }
        }
        levelStart = dummy.next;                  // go down one level
    }
    return root;
}