# Number of Good Leaf Nodes Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-good-leaf-nodes-pairs)
Canonical: https://scaleengineer.com/dsa/problems/number-of-good-leaf-nodes-pairs
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
You are given the `root` of a binary tree and an integer `distance`. A pair of two different **leaf** nodes of a binary tree is said to be good if the length of **the shortest path** between them is less than or equal to `distance`.

Return _the number of good leaf node pairs_ in the tree.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-good-leaf-nodes-pairs/image0.jpg) 

**Input:** root = [1,2,3,null,4], distance = 3
**Output:** 1
**Explanation:** The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

**Example 2:**

![](https://assets.glich.co/dsa/number-of-good-leaf-nodes-pairs/image1.jpg) 

**Input:** root = [1,2,3,4,5,6,7], distance = 3
**Output:** 2
**Explanation:** The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

**Example 3:**

**Input:** root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
**Output:** 1
**Explanation:** The only good pair is [2,5].

**Constraints:**

* The number of nodes in the `tree` is in the range `[1, 210].`
* `1 <= Node.val <= 100`
* `1 <= distance <= 10`

# Approaches
## Brute Force: Find All Leaf Pairs and Calculate Distance
This approach is the most straightforward but also the least efficient. It involves three main steps: first, identify all the leaf nodes in the tree. Second, generate all unique pairs of these leaf nodes. Third, for each pair, calculate the shortest path distance between them and check if it's within the given `distance`.
**Time:** O(N^2 * H) or O(N^3) in the worst case. Let N be the number of nodes and H be the height. Finding all L leaves takes O(N). There are O(L^2) pairs of leaves. For each pair, finding the LCA takes O(H) and finding distances from LCA takes O(H). Since L can be O(N) and H can be O(N), the total complexity is O(L^2 * H) which simplifies to O(N^3) in the worst-case scenario of a skewed tree. · **Space:** O(N). We need O(L) space to store the leaf nodes, where L can be O(N). The recursion stack for DFS/LCA can also go up to O(N) in the worst case of a skewed tree.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient and will likely time out for larger inputs.; Involves multiple traversals of the tree for each pair of leaves.
### Explanation
```java
class Solution {
    // Finds all leaf nodes and stores them in a list.
    private void findLeaves(TreeNode node, List<TreeNode> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            leaves.add(node);
            return;
        }
        findLeaves(node.left, leaves);
        findLeaves(node.right, leaves);
    }

    // Finds the Lowest Common Ancestor of two nodes.
    private TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = findLCA(root.left, p, q);
        TreeNode right = findLCA(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

    // Finds the distance from an ancestor to a target node.
    private int findDistance(TreeNode ancestor, TreeNode target, int depth) {
        if (ancestor == null) return -1;
        if (ancestor == target) return depth;
        int leftDist = findDistance(ancestor.left, target, depth + 1);
        if (leftDist != -1) return leftDist;
        return findDistance(ancestor.right, target, depth + 1);
    }

    public int countPairs(TreeNode root, int distance) {
        List<TreeNode> leaves = new ArrayList<>();
        findLeaves(root, leaves);
        
        int count = 0;
        for (int i = 0; i < leaves.size(); i++) {
            for (int j = i + 1; j < leaves.size(); j++) {
                TreeNode leaf1 = leaves.get(i);
                TreeNode leaf2 = leaves.get(j);
                
                TreeNode lca = findLCA(root, leaf1, leaf2);
                int dist = findDistance(lca, leaf1, 0) + findDistance(lca, leaf2, 0);
                
                if (dist <= distance) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- **Find Leaf Nodes**: Traverse the entire tree using a Depth-First Search (DFS) or Breadth-First Search (BFS). If a node has no left and no right child, add it to a list of `leafNodes`.
- **Iterate Through Pairs**: Use two nested loops to iterate through all unique pairs of leaf nodes `(leaf1, leaf2)` from the `leafNodes` list.
- **Calculate Distance**: For each pair, calculate the shortest distance. The shortest path between two nodes in a tree always passes through their Lowest Common Ancestor (LCA). The distance can be calculated as: `distance(leaf1, leaf2) = dist(leaf1, LCA) + dist(leaf2, LCA)`. This can also be expressed in terms of node depths from the root: `depth(leaf1) + depth(leaf2) - 2 * depth(LCA(leaf1, leaf2))`. You'll need helper functions to find the LCA of two nodes and to find the distance from an ancestor to a descendant.
- **Count Good Pairs**: If the calculated distance is less than or equal to the given `distance`, increment a counter.
- **Return Count**: After checking all pairs, return the final count.

## Graph Conversion and BFS from Each Leaf
A more optimized approach involves treating the tree as an undirected graph. We first convert the binary tree into an adjacency list representation. Then, for each leaf node, we perform a Breadth-First Search (BFS) to find all other leaf nodes within the given `distance`.
**Time:** O(N*L), where N is the number of nodes and L is the number of leaves. Building the graph and finding L leaves takes O(N). Then, we perform a BFS from each of the L leaf nodes. Each BFS can take up to O(N) time as it might traverse the entire graph. Since L can be O(N), the total time is O(L * N) which is O(N^2) in the worst case. · **Space:** O(N). The adjacency list requires O(N) space. The list of leaves requires O(L) space (where L is the number of leaves). The BFS queue and visited set also require O(N) space in the worst case.
**Pros:** More efficient than the brute-force approach.; Correctly models the problem as a shortest path problem on a graph.
**Cons:** Still potentially too slow if the number of leaves is large.; Requires extra space to build the graph representation.
### Explanation
```java
class Solution {
    public int countPairs(TreeNode root, int distance) {
        Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
        List<TreeNode> leaves = new ArrayList<>();
        buildGraph(root, null, graph, leaves);
        
        int count = 0;
        for (TreeNode leaf : leaves) {
            Queue<TreeNode> queue = new LinkedList<>();
            Set<TreeNode> visited = new HashSet<>();
            
            queue.add(leaf);
            visited.add(leaf);
            
            for (int level = 0; level <= distance; level++) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    if (curr != leaf && curr.left == null && curr.right == null) {
                        count++;
                    }
                    if (graph.containsKey(curr)) {
                        for (TreeNode neighbor : graph.get(curr)) {
                            if (!visited.contains(neighbor)) {
                                visited.add(neighbor);
                                queue.add(neighbor);
                            }
                        }
                    }
                }
            }
        }
        return count / 2;
    }

    private void buildGraph(TreeNode node, TreeNode parent, Map<TreeNode, List<TreeNode>> graph, List<TreeNode> leaves) {
        if (node == null) return;
        
        if (node.left == null && node.right == null) {
            leaves.add(node);
        }
        
        graph.putIfAbsent(node, new ArrayList<>());
        if (parent != null) {
            graph.get(node).add(parent);
            graph.putIfAbsent(parent, new ArrayList<>());
            graph.get(parent).add(node);
        }
        
        buildGraph(node.left, node, graph, leaves);
        buildGraph(node.right, node, graph, leaves);
    }
}
```
### Algorithm
- **Build Graph and Find Leaves**: Traverse the tree once (using DFS). During the traversal, build an adjacency list where each node is connected to its parent and children. Simultaneously, identify and store all leaf nodes in a separate list.
- **Iterate and Perform BFS**: Iterate through each leaf node in the `leaves` list.
- **BFS Traversal**: For each `startLeaf`, initiate a BFS. The BFS explores the graph layer by layer, keeping track of the distance from `startLeaf` and a set of visited nodes to avoid redundant computations.
- **Find Good Pairs**: During the BFS, if we encounter another leaf node `endLeaf` at a distance `d` such that `d <= distance`, we've found a good pair.
- **Count and Avoid Duplicates**: Increment a counter for each good pair found. Since this process will find both `(A, B)` and `(B, A)`, the final result should be divided by 2.

## Optimal: Post-order Traversal with Distance Propagation
The most efficient solution uses a single post-order traversal (DFS). For each node, the recursive function calculates the distances to all leaf nodes in its subtree. When returning from the recursive calls for its children, a node can use the lists of leaf distances from its left and right subtrees to count the 'good pairs' that have this node as their lowest common ancestor. The key insight is that the path between a leaf in the left subtree and a leaf in the right subtree must pass through the current node.
**Time:** O(N * D^2), where N is the number of nodes and D is the `distance`. We visit each node once. At each node, we process two lists of distances from its children. Due to the pruning (`d + 1 < distance`), the size of these lists is at most D. The nested loop to count pairs takes O(D^2) time. Thus, the total time is O(N * D^2). · **Space:** O(N * D). The recursion depth can be up to N (the height of the tree). At each level of the recursion, we store a list of distances of size at most D. In the worst case of a skewed tree, this leads to a space complexity of O(N * D).
**Pros:** Most efficient solution, using a single pass over the tree.; Effectively uses the `distance` constraint to prune the search space and keep intermediate data structures small.
**Cons:** The logic is more complex to reason about compared to the brute-force approaches.
### Explanation
```java
class Solution {
    int result = 0;

    public int countPairs(TreeNode root, int distance) {
        dfs(root, distance);
        return result;
    }

    private List<Integer> dfs(TreeNode node, int distance) {
        if (node == null) {
            return new ArrayList<>();
        }

        if (node.left == null && node.right == null) {
            List<Integer> leafDist = new ArrayList<>();
            leafDist.add(1);
            return leafDist;
        }

        List<Integer> leftDists = dfs(node.left, distance);
        List<Integer> rightDists = dfs(node.right, distance);

        // Count pairs with LCA as current node
        for (int d1 : leftDists) {
            for (int d2 : rightDists) {
                if (d1 + d2 <= distance) {
                    result++;
                }
            }
        }

        // Prepare distances for the parent node
        List<Integer> parentDists = new ArrayList<>();
        for (int d : leftDists) {
            if (d + 1 < distance) { // Pruning
                parentDists.add(d + 1);
            }
        }
        for (int d : rightDists) {
            if (d + 1 < distance) { // Pruning
                parentDists.add(d + 1);
            }
        }

        return parentDists;
    }
}
```
### Algorithm
- **DFS with Return Value**: We define a recursive helper function, say `dfs(node)`, that performs a post-order traversal. This function will return a list of distances from `node` to each leaf in its subtree.
- **Base Cases**:
    - If the current node is `null`, return an empty list.
    - If the current node is a leaf node, return a list containing just the distance `1` (representing the distance to its parent).
- **Recursive Step**: For an internal node:
    - Recursively call `dfs` on the left child to get `leftDistances`.
    - Recursively call `dfs` on the right child to get `rightDistances`.
- **Count Pairs**: Iterate through all pairs of distances `(d1, d2)` where `d1` is from `leftDistances` and `d2` is from `rightDistances`. The total path length for the corresponding leaves is `d1 + d2`. If `d1 + d2 <= distance`, increment a global counter.
- **Propagate Distances Up**: Create a new list of distances to return to the parent. For each distance `d` in `leftDistances` and `rightDistances`, add `d + 1` to the new list, but only if `d + 1 < distance`. This pruning step is crucial for efficiency, as it keeps the size of the distance lists small.
- **Return Result**: The main function initializes a counter to 0, calls `dfs(root)`, and returns the final count.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int countPairs ( TreeNode root , int distance ) { if ( root == null ) { return 0 ; } int ans = countPairs ( root . left , distance ) + countPairs ( root . right , distance ); int [] cnt1 = new int [ distance ]; int [] cnt2 = new int [ distance ]; dfs ( root . left , cnt1 , 1 ); dfs ( root . right , cnt2 , 1 ); for ( int i = 0 ; i < distance ; ++ i ) { for ( int j = 0 ; j < distance ; ++ j ) { if ( i + j <= distance ) { ans += cnt1 [ i ] * cnt2 [ j ]; } } } return ans ; } void dfs ( TreeNode root , int [] cnt , int i ) { if ( root == null || i >= cnt . length ) { return ; } if ( root . left == null && root . right == null ) { ++ cnt [ i ]; return ; } dfs ( root . left , cnt , i + 1 ); dfs ( root . right , cnt , i + 1 ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} distance * @return {number} */ var countPairs =
  function (root, distance) {
    const pairs = [];
    const dfs = (node) => {
      if (!node) return [];
      if (!node.left && !node.right) return [[node.val, 1]];
      const left = dfs(node.left);
      const right = dfs(node.right);
      for (const [x, dx] of left) {
        for (const [y, dy] of right) {
          if (dx + dy <= distance) {
            pairs.push([x, y]);
          }
        }
      }
      const res = [];
      for (const arr of [left, right]) {
        for (const x of arr) {
          if (++x[1] <= distance) res.push(x);
        }
      }
      return res;
    };
    dfs(root);
    return pairs.length;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countPairs ( TreeNode * root , int distance ) { if ( ! root ) return 0 ; int ans = countPairs ( root -> left , distance ) + countPairs ( root -> right , distance ); vector < int > cnt1 ( distance ); vector < int > cnt2 ( distance ); dfs ( root -> left , cnt1 , 1 ); dfs ( root -> right , cnt2 , 1 ); for ( int i = 0 ; i < distance ; ++ i ) { for ( int j = 0 ; j < distance ; ++ j ) { if ( i + j <= distance ) { ans += cnt1 [ i ] * cnt2 [ j ]; } } } return ans ; } void dfs ( TreeNode * root , vector < int >& cnt , int i ) { if ( ! root || i >= cnt . size ()) return ; if ( ! root -> left && ! root -> right ) { ++ cnt [ i ]; return ; } dfs ( root -> left , cnt , i + 1 ); dfs ( root -> right , cnt , i + 1 ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def countPairs ( self , root : TreeNode , distance : int ) -> int : def dfs ( root , cnt , i ): if root is None or i >= distance : return if root . left is None and root . right is None : cnt [ i ] += 1 return dfs ( root . left , cnt , i + 1 ) dfs ( root . right , cnt , i + 1 ) if root is None : return 0 ans = self . countPairs ( root . left , distance ) + self . countPairs ( root . right , distance ) cnt1 = Counter () cnt2 = Counter () dfs ( root . left , cnt1 , 1 ) dfs ( root . right , cnt2 , 1 ) for k1 , v1 in cnt1 . items (): for k2 , v2 in cnt2 . items (): if k1 + k2 <= distance : ans += v1 * v2 return ans
```