Number of Good Leaf Nodes Pairs: DFS Distance Propagation

You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes is called "good" if the shortest path between them is less than or equal to distance. Return the number of good leaf node pairs in the tree.

This is LeetCode 1530: Number of Good Leaf Nodes Pairs, and it teaches you one of the most versatile patterns in tree recursion: propagating distance information upward from leaves and combining results at internal nodes. Once you see how this works, you will recognize the same structure in many other tree problems.

Why this problem matters

Many tree problems follow a common shape. You need information from the leaves, but you can only discover it by recursing down first and then passing results back up. This problem is a clean example of that post-order DFS pattern.

The twist here is that each node does not return a single value. It returns a list of distances, one for each leaf in its subtree. At every internal node, you combine the left and right lists to count good pairs, then pass the merged (and incremented) list up to the parent.

This "combine left and right subtree results" pattern shows up in problems like Diameter of Binary Tree, Binary Tree Maximum Path Sum, and many others. Mastering it here gives you a template you can reuse.

The key insight

Think about what happens at any internal node. Its left subtree contains some leaves, and its right subtree contains other leaves. The shortest path between a left-subtree leaf and a right-subtree leaf always goes through this node.

If a leaf in the left subtree is at distance dL from the current node, and a leaf in the right subtree is at distance dR, then the path between them has length dL + dR. If that sum is <= distance, it is a good pair.

So the algorithm is:

1. At each leaf, return [1] to the parent (meaning "there is a leaf at distance 1 from you").
2. At each internal node, get the distance lists from the left and right children.
3. For every combination of one left distance and one right distance, check if their sum is <= distance. If so, increment the count.
4. Merge the two lists, add 1 to every distance (since the parent is one edge farther away), and return the merged list upward.
5. Filter out any distances that already exceed distance, since they can never form a good pair higher up.

The solution

def count_pairs(root, distance):
    count = 0

    def dfs(node):
        nonlocal count
        if node is None:
            return []
        if node.left is None and node.right is None:
            return [1]

        left_distances = dfs(node.left)
        right_distances = dfs(node.right)

        for dl in left_distances:
            for dr in right_distances:
                if dl + dr <= distance:
                    count += 1

        return [d + 1 for d in left_distances + right_distances if d + 1 <= distance]

    dfs(root)
    return count

Let's walk through each piece:

• count = 0 initializes the global counter for good pairs. Every internal node may add to this.
• if node is None: return [] is the base case. A null child contributes no leaves.
• if node.left is None and node.right is None: return [1] handles leaf nodes. The leaf is at distance 1 from its parent.
• left_distances = dfs(node.left) collects distances from all leaves in the left subtree.
• right_distances = dfs(node.right) collects distances from all leaves in the right subtree.
• The nested loop checks every pair of one left leaf and one right leaf. If their distances sum to <= distance, that is a good pair.
• The return statement merges both lists, increments each distance by 1 (since the parent is one edge farther), and filters out any distance that already exceeds the limit.

Visual walkthrough

Let's trace the DFS on the tree [1, 2, 3, 4, 5, null, 6] with distance = 3. At each node, watch what distance list gets returned and how pairs are counted.

The critical moment is Step 2. At node 2, the left child returns [1] and the right child returns [1]. We check the single pair: 1 + 1 = 2, which is within our distance limit of 3. That gives us 1 good pair. Later at the root, the cross-subtree distances are all 4, which exceeds the limit. So the final answer is 1.

Complexity analysis

Here n is the number of nodes and d is the distance parameter.

Time: We visit every node once. At each internal node, we compare all pairs of left and right distances. Since we prune distances greater than d, each list has at most d entries. Comparing two lists of size up to d takes O(d^2) per node. Total: O(n * d^2). Given the constraint that d is at most 10, this is effectively O(100n), which is linear in practice.

Space: The recursion stack goes up to O(n) in the worst case (a skewed tree). Each node's distance list has at most d entries. The total space across all active stack frames is O(n * d). With d bounded at 10, this is effectively O(n).

The building blocks

1. Post-order DFS with upward propagation

The core pattern here is post-order traversal: process children first, then use their results at the current node. This is the same structure used in computing tree height, diameter, and many other tree metrics.

def dfs(node):
    if node is None:
        return []
    left = dfs(node.left)
    right = dfs(node.right)
    result = combine(left, right)
    return result

The key is that the recursive call returns useful information (distances from leaves) that the parent needs. You always recurse first, then process.

2. Distance list merging and pruning

At each node, you merge the left and right distance lists, increment every value by 1, and drop values that exceed the limit.

merged = [d + 1 for d in left + right if d + 1 <= distance]

This pruning keeps the lists small. Without it, every leaf in the tree would contribute a distance entry all the way up to the root, and the lists could grow to size O(n). With pruning, they stay at most size O(d).

Edge cases

• Single node (just a root with no children): There are no leaf pairs at all. Return 0.
• All leaves are directly connected to the root: Every leaf is at distance 1. Every pair has path length 2. If distance >= 2, all pairs are good.
• Skewed tree (every node has only one child): There is only one leaf. You need at least two leaves to form a pair. Return 0.
• distance = 1: The only good pairs would be two leaves sharing the same parent, each at distance 1. Their path would be 2, which exceeds 1. So the answer is always 0 when distance = 1.
• Large distance value: When distance is large enough, every pair of leaves is good. The answer becomes C(L, 2) where L is the number of leaves.

From understanding to recall

This problem tests whether you can apply the post-order DFS pattern with a twist: instead of returning a single value, you return a list. The steps to internalize are:

1. Recognize that leaf pairs in different subtrees must have their path go through the subtree's root.
2. See that tracking distances from leaves lets you count valid pairs at each node.
3. Remember to increment distances as you move up and prune entries that can never contribute.

Practice reconstructing the solution from scratch. Start with the base cases, then build up the recursive case. The pattern of "return a list of distances, combine at internal nodes, count valid pairs" is the core idea.

Related posts

• Diameter of Binary Tree - Another tree problem propagating info upward from leaves
• Binary Tree Maximum Path Sum - Combining left and right subtree results at each node
• All Nodes Distance K in Binary Tree - Finding nodes at a given distance in a tree

If you want to build lasting fluency with tree patterns like this one, CodeBricks uses spaced repetition to help you drill these problems at the right intervals. Instead of grinding through random lists, you practice the patterns that matter, right when you are about to forget them.