← all categories

Tree Center a515b4b4

Tree center(s) via leaf-peeling (repeatedly strip degree-1 nodes). Returns 1 node if the tree's diameter is even, 2 adjacent nodes if odd.

Time: O(n). tested

content/graphs/tree-center.h

vector<int> treeCenters(vector<vector<int>> &adj) {
    int n = (int)adj.size();
    vector<int> degree(n);
    queue<int> leaves;
    for (int i = 0; i < n; i++) {
        degree[i] = (int)adj[i].size();
        if (degree[i] <= 1) leaves.push(i);
    }

    int left = n;
    while (left > 2) {
        int cnt = (int)leaves.size();
        left -= cnt;
        for (int i = 0; i < cnt; i++) {
            int leaf = leaves.front(); leaves.pop();
            for (int v : adj[leaf]) {
                degree[v]--;
                if (degree[v] == 1) leaves.push(v);
            }
        }
    }

    vector<int> centers;
    while (!leaves.empty()) { centers.push_back(leaves.front()); leaves.pop(); }
    return centers;
}