owlingcode

Tree Fundamentals

Trees are connected acyclic graphs that form the backbone of many algorithmic problems. Understanding tree properties and traversal methods is essential for solving complex tree-based challenges.

Tree Representation

// Adjacency list representation
vector<vector<int>> adj;
vector<int> parent;
vector<int> depth;

// Build tree from edges
void buildTree(int n, vector<pair<int, int>>& edges) {
    adj.assign(n, vector<int>());
    parent.assign(n, -1);
    depth.assign(n, 0);
    
    for(auto& edge : edges) {
        int u = edge.first, v = edge.second;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

// Root the tree and compute parent/depth
void rootTree(int root, int par = -1, int d = 0) {
    parent[root] = par;
    depth[root] = d;
    
    for(int child : adj[root]) {
        if(child != par) {
            rootTree(child, root, d + 1);
        }
    }
}
                    

Tree Traversal Algorithms

Different traversal methods serve different purposes in tree algorithms:

DFS Traversal Orders

vector<int> preorder, inorder, postorder;

void dfsTraversal(int node, int parent = -1) {
    // Preorder: visit node before children
    preorder.push_back(node);
    
    for(int child : adj[node]) {
        if(child != parent) {
            dfsTraversal(child, node);
        }
    }
    
    // Postorder: visit node after children
    postorder.push_back(node);
}

// For binary trees with explicit left/right children
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorderTraversal(TreeNode* root, vector<int>& result) {
    if(!root) return;
    
    inorderTraversal(root->left, result);
    result.push_back(root->val);  // Inorder: left, root, right
    inorderTraversal(root->right, result);
}

// Iterative DFS using stack
vector<int> iterativeDFS(int root) {
    vector<int> result;
    stack<int> st;
    vector<bool> visited(adj.size(), false);
    
    st.push(root);
    
    while(!st.empty()) {
        int node = st.top();
        st.pop();
        
        if(!visited[node]) {
            visited[node] = true;
            result.push_back(node);
            
            // Add children in reverse order for correct traversal
            for(int i = adj[node].size() - 1; i >= 0; i--) {
                int child = adj[node][i];
                if(!visited[child]) {
                    st.push(child);
                }
            }
        }
    }
    
    return result;
}
                    

Tree Diameter

The diameter is the longest path between any two nodes in the tree. We can find it using two DFS calls:

pair<int, int> bfsFarthest(int start) {
    queue<int> q;
    vector<int> dist(adj.size(), -1);
    
    q.push(start);
    dist[start] = 0;
    
    int farthest = start, maxDist = 0;
    
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        
        for(int neighbor : adj[node]) {
            if(dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
                
                if(dist[neighbor] > maxDist) {
                    maxDist = dist[neighbor];
                    farthest = neighbor;
                }
            }
        }
    }
    
    return {farthest, maxDist};
}

// Find tree diameter
pair<int, vector<int>> findDiameter() {
    // First BFS to find one end of diameter
    auto [end1, _] = bfsFarthest(0);
    
    // Second BFS to find actual diameter
    auto [end2, diameter] = bfsFarthest(end1);
    
    // Reconstruct diameter path
    vector<int> diameterPath;
    // ... path reconstruction logic
    
    return {diameter, diameterPath};
}

// Alternative: Tree DP approach for diameter
vector<int> maxDepth1, maxDepth2; // Two largest depths from each node
int treeDiameter = 0;

void treeDiameterDP(int node, int parent = -1) {
    maxDepth1[node] = maxDepth2[node] = 0;
    
    for(int child : adj[node]) {
        if(child != parent) {
            treeDiameterDP(child, node);
            
            int childDepth = maxDepth1[child] + 1;
            
            if(childDepth > maxDepth1[node]) {
                maxDepth2[node] = maxDepth1[node];
                maxDepth1[node] = childDepth;
            } else if(childDepth > maxDepth2[node]) {
                maxDepth2[node] = childDepth;
            }
        }
    }
    
    // Update global diameter
    treeDiameter = max(treeDiameter, maxDepth1[node] + maxDepth2[node]);
}
                    

Lowest Common Ancestor (LCA)

LCA algorithms help find the lowest common ancestor of two nodes efficiently:

Binary Lifting LCA

class LCA {
private:
    int n, LOG;
    vector<vector<int>> up;
    vector<int> depth;
    vector<vector<int>>& adj;
    
public:
    LCA(vector<vector<int>>& _adj, int root = 0) : adj(_adj) {
        n = adj.size();
        LOG = ceil(log2(n)) + 1;
        up.assign(n, vector<int>(LOG, -1));
        depth.assign(n, 0);
        
        dfs(root, -1);
        preprocess();
    }
    
    void dfs(int node, int parent) {
        up[node][0] = parent;
        for(int child : adj[node]) {
            if(child != parent) {
                depth[child] = depth[node] + 1;
                dfs(child, node);
            }
        }
    }
    
    void preprocess() {
        for(int j = 1; j < LOG; j++) {
            for(int i = 0; i < n; i++) {
                if(up[i][j-1] != -1) {
                    up[i][j] = up[up[i][j-1]][j-1];
                }
            }
        }
    }
    
    int lca(int a, int b) {
        if(depth[a] < depth[b]) swap(a, b);
        
        // Bring a to same level as b
        int diff = depth[a] - depth[b];
        for(int i = 0; i < LOG; i++) {
            if(diff & (1 << i)) {
                a = up[a][i];
            }
        }
        
        if(a == b) return a;
        
        // Binary search for LCA
        for(int i = LOG - 1; i >= 0; i--) {
            if(up[a][i] != up[b][i]) {
                a = up[a][i];
                b = up[b][i];
            }
        }
        
        return up[a][0];
    }
    
    int distance(int a, int b) {
        return depth[a] + depth[b] - 2 * depth[lca(a, b)];
    }
    
    bool isAncestor(int ancestor, int node) {
        return lca(ancestor, node) == ancestor;
    }
};
                    

Euler Tour LCA

class EulerTourLCA {
private:
    vector<int> euler, depth, first;
    vector<vector<int>> st; // Sparse table for RMQ
    
public:
    EulerTourLCA(vector<vector<int>>& adj, int root = 0) {
        int n = adj.size();
        first.assign(n, -1);
        
        // Build Euler tour
        eulerTour(root, -1, 0, adj);
        
        // Build sparse table for RMQ
        buildSparseTable();
    }
    
    void eulerTour(int node, int parent, int d, vector<vector<int>>& adj) {
        if(first[node] == -1) first[node] = euler.size();
        
        euler.push_back(node);
        depth.push_back(d);
        
        for(int child : adj[node]) {
            if(child != parent) {
                eulerTour(child, node, d + 1, adj);
                euler.push_back(node);
                depth.push_back(d);
            }
        }
    }
    
    void buildSparseTable() {
        int m = euler.size();
        int k = floor(log2(m)) + 1;
        st.assign(k, vector<int>(m));
        
        for(int i = 0; i < m; i++) {
            st[0][i] = i;
        }
        
        for(int j = 1; j < k; j++) {
            for(int i = 0; i + (1 << j) <= m; i++) {
                int left = st[j-1][i];
                int right = st[j-1][i + (1 << (j-1))];
                st[j][i] = (depth[left] < depth[right]) ? left : right;
            }
        }
    }
    
    int lca(int a, int b) {
        int left = first[a], right = first[b];
        if(left > right) swap(left, right);
        
        int len = right - left + 1;
        int k = floor(log2(len));
        
        int idx1 = st[k][left];
        int idx2 = st[k][right - (1 << k) + 1];
        
        return (depth[idx1] < depth[idx2]) ? euler[idx1] : euler[idx2];
    }
};
                    

Tree Dynamic Programming

Many tree problems can be solved efficiently using dynamic programming on trees:

Tree DP Template

// Tree DP for maximum independent set
vector<int> dpInclude, dpExclude; // Include/exclude current node

void treeDPMaxIndependentSet(int node, int parent = -1) {
    dpInclude[node] = 1; // Include current node
    dpExclude[node] = 0; // Exclude current node
    
    for(int child : adj[node]) {
        if(child != parent) {
            treeDPMaxIndependentSet(child, node);
            
            // If we include current node, we cannot include children
            dpInclude[node] += dpExclude[child];
            
            // If we exclude current node, we can choose optimally for children
            dpExclude[node] += max(dpInclude[child], dpExclude[child]);
        }
    }
}

// Tree DP for subtree sizes
vector<int> subtreeSize;

void calculateSubtreeSizes(int node, int parent = -1) {
    subtreeSize[node] = 1;
    
    for(int child : adj[node]) {
        if(child != parent) {
            calculateSubtreeSizes(child, node);
            subtreeSize[node] += subtreeSize[child];
        }
    }
}

// Tree DP for distance sums
vector<long long> distSum; // Sum of distances from each node to all others
vector<int> subtreeSize;

void calculateDistSums(int node, int parent = -1) {
    subtreeSize[node] = 1;
    distSum[node] = 0;
    
    for(int child : adj[node]) {
        if(child != parent) {
            calculateDistSums(child, node);
            subtreeSize[node] += subtreeSize[child];
            distSum[node] += distSum[child] + subtreeSize[child];
        }
    }
}

// Re-root the tree to calculate answer for all nodes
void reroot(int node, int parent = -1, int n = 0) {
    for(int child : adj[node]) {
        if(child != parent) {
            // Move root from node to child
            long long oldDistSum = distSum[child];
            int oldSubtreeSize = subtreeSize[child];
            
            // Update child as new root
            distSum[child] = distSum[node] - subtreeSize[child] + (n - subtreeSize[child]);
            subtreeSize[child] = n;
            
            reroot(child, node, n);
            
            // Restore values
            distSum[child] = oldDistSum;
            subtreeSize[child] = oldSubtreeSize;
        }
    }
}