1530. Number of Good Leaf Nodes Pairs

📝 Problem Details

• Title: 1530. Number of Good Leaf Nodes Pairs
• Link: https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/
• Difficulty: Medium
• Tags/Categories: Trees DFS BFS Graphs

💭What Were My Initial Thoughts?

- The problem involves finding pairs of leaf nodes with a distance constraint.
- Initially thought of converting the tree into a graph and applying shortest path algorithms.
- Alternatively, a tree-based DFS to traverse leaf nodes seemed viable:
  - Conduct a DFS to identify leaf nodes.
  - Perform nested traversal to compute distances between leaf nodes, pruning if the distance exceeds the given limit.
  - Optimize traversal to avoid redundant computations.
- However, this naive approach is inefficient and likely to result in TLE (Time Limit Exceeded).

🤔What Did I Struggle With?

- Struggled to handle redundant computations in the nested traversal.
- Ensuring the distance constraint was respected efficiently.
- Managing the exponential growth of pair comparisons in the naive approach.

💡 Explanation of Solution (DFS + Prefix Sum)

A more efficient solution leverages post-order traversal (DFS) with prefix sum counting:

1. Traverse the tree in a post-order fashion.

2. At each node, maintain a frequency array (`distanceCount`)
	-`distanceCount[i]` represents the number of leaf nodes at distance `i` from the current node.

3. Combine frequency arrays from left and right child nodes to compute the number of good pairs:
	- For each pair of distances `i` from the left child and `j` from the right child, 
	- check if `i + j + 2 <= distance`.

4. Update the current node's frequency array by incrementing distances (i.e., shifting the array).
5. Return the total count of good pairs at the root.

⌛ Complexity Analysis (DFS + Prefix Sum)

Time Complexity: O(n * d)
	- where `n` is the number of nodes in the tree and `d` is the given `distance`. 
	- each node processes its children with a frequency array of size `d`.

Space Complexity: O(n + d)
	- accounting for the recursion stack (`O(n)`) and frequency arrays (`O(d)`).

💻 Implementation of Solution (DFS + Prefix Sum)

class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        int result = 0;
        helper(root, distance, result);
        return result;
    }
 
private:
    vector<int> helper(TreeNode* node, int distance, int& result) {
        if (!node) return vector<int>(distance + 1, 0);
 
        // Base case: If the node is a leaf, return a frequency array with distance 1.
        if (!node->left && !node->right) {
            vector<int> leafCounts(distance + 1, 0);
            leafCounts[1] = 1;
            return leafCounts;
        }
 
        // Recursive case: Get frequency arrays from left and right children.
        vector<int> leftCounts = helper(node->left, distance, result);
        vector<int> rightCounts = helper(node->right, distance, result);
 
        // Count good pairs by combining left and right frequency arrays.
        for (int i = 1; i <= distance; ++i) {
            for (int j = 1; j <= distance; ++j) {
                if (i + j <= distance) {
                    result += leftCounts[i] * rightCounts[j];
                }
            }
        }
 
        // Shift distances up by 1 and combine results into the current node's frequency array.
        vector<int> currentCounts(distance + 1, 0);
        for (int i = 1; i < distance; ++i) {
            currentCounts[i + 1] = leftCounts[i] + rightCounts[i];
        }
 
        return currentCounts;
    }
};

---

💡 Explanation of Solution (Graph Conversion + BFS)

- Convert the tree into an undirected graph:
  1. Use an adjacency list to represent connections between nodes.
  2. Identify all leaf nodes during the graph construction.
- For each leaf node, perform a Breadth-First Search (BFS) to calculate distances to all other leaf nodes:
  - Stop the BFS early if the distance exceeds the given `distance` parameter.
  - Count pairs of leaf nodes that satisfy the distance condition.
- Return the total count of good leaf node pairs.

⌛ Complexity Analysis (Graph Conversion + BFS)

Time Complexity: O(n + m + l^2), where:
  - `n` is the number of nodes in the tree.
  - `m` is the number of edges (equal to `n - 1` in a tree).
  - `l` is the number of leaf nodes. Each leaf node performs a BFS over other leaf nodes, leading to a worst-case `O(l^2)` complexity for pairwise comparisons.

Space Complexity: O(n), for the adjacency list and BFS queue.

💻 Implementation of Solution (Graph Conversion + BFS)

class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        int result = 0;
        helper(root, distance, result);
        return result;
    }
 
private:
    vector<int> helper(TreeNode* node, int distance, int& result) {
        if (!node) return vector<int>(distance + 1, 0);
 
        // Base case: If the node is a leaf, return a frequency array with distance 1.
        if (!node->left && !node->right) {
            vector<int> leafCounts(distance + 1, 0);
            leafCounts[1] = 1;
            return leafCounts;
        }
 
        // Recursive case: Get frequency arrays from left and right children.
        vector<int> leftCounts = helper(node->left, distance, result);
        vector<int> rightCounts = helper(node->right, distance, result);
 
        // Count good pairs by combining left and right frequency arrays.
        for (int i = 1; i <= distance; ++i) {
            for (int j = 1; j <= distance; ++j) {
                if (i + j <= distance) {
                    result += leftCounts[i] * rightCounts[j];
                }
            }
        }
 
        // Shift distances up by 1 and combine results into the current node's frequency array.
        vector<int> currentCounts(distance + 1, 0);
        for (int i = 1; i < distance; ++i) {
            currentCounts[i + 1] = leftCounts[i] + rightCounts[i];
        }
 
        return currentCounts;
    }
};