Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

LeetCode 1530 - Number of Good Leaf Nodes Pairs

Problem Understanding

This problem gives us the root of a binary tree and an integer distance. We need to count how many pairs of leaf nodes satisfy a specific condition: the shortest path between the two leaves must be less than or equal to distance.

A leaf node is a node with no left child and no right child.

The shortest path between two nodes in a tree is the number of edges along the unique path connecting them. Since a tree contains no cycles, every pair of nodes has exactly one path between them.

For example, suppose two leaves share the same parent. The path between them goes:

from the first leaf up to the parent
then down to the second leaf

That path length is 2.

The input consists of:

root, the root node of a binary tree
distance, the maximum allowed distance between two leaves

The output is a single integer representing the number of good leaf pairs.

The constraints are important:

The tree contains at most 2^10 = 1024 nodes
distance <= 10

The small maximum distance is the key observation that enables an efficient solution. Even though the tree may contain many leaves, we only care about leaf distances up to 10, which allows us to keep compact distance information during traversal.

There are several edge cases that can cause issues in naive implementations:

A tree with only one node has no pair of leaves, so the answer is 0
Highly unbalanced trees may create long paths
Multiple leaves may exist entirely within one subtree
Leaf pairs can only be counted once, even though traversal processes many recursive calls
Distances must count edges, not nodes

The problem guarantees a valid binary tree and guarantees that distance >= 1.

Approaches

Brute Force Approach

The most direct solution is to first collect all leaf nodes, then compute the shortest distance between every pair of leaves.

One way to do this is:

Traverse the tree and store all leaf nodes.
For every pair of leaves:

Find the distance between them.
If the distance is at most distance, increment the answer.

To compute distances efficiently, we could:

build parent pointers,
run BFS from one leaf to another,
or compute Lowest Common Ancestors.

This approach is correct because every pair of leaves is explicitly checked.

However, it becomes inefficient because:

If there are L leaves, we must check O(L^2) pairs.
Computing each distance may take O(N) time.

In the worst case, the total complexity becomes O(L^2 * N).

Although the constraints here are relatively small, this approach does unnecessary repeated work.

Optimal DFS + Distance Aggregation Approach

The key insight is that we do not actually need distances between every pair of leaves globally.

Instead, while performing a postorder DFS traversal, each subtree can return information about how far its leaf nodes are from the current node.

For each node:

recursively gather leaf distances from the left subtree
recursively gather leaf distances from the right subtree
combine them to count valid pairs passing through the current node
return updated distances upward

This works because every shortest path between two leaves passes through their lowest common ancestor. When processing a node, we can determine all valid pairs whose path goes through that node.

Since distance <= 10, each subtree only needs to store a small number of distances, making the solution efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(L² × N)	O(N)	Explicitly checks every leaf pair
Optimal DFS	O(N × D²)	O(H + D)	Aggregates leaf distances bottom up

Here:

N is the number of nodes
L is the number of leaves
D is distance
H is the tree height

Because distance <= 10, D² is effectively constant.

Algorithm Walkthrough

Step 1: Perform a postorder DFS traversal

We process children before the parent because the parent needs information about leaf distances from both subtrees.

Each recursive call returns a list of distances from the current node to all leaf nodes inside that subtree.

Step 2: Handle the leaf node case

If the current node is a leaf:

return [1]

The value 1 means:

from the current node's parent,
this leaf is exactly one edge away.

This convention simplifies upward propagation.

Step 3: Recursively gather left and right subtree distances

For a non-leaf node:

recursively collect leaf distances from the left child
recursively collect leaf distances from the right child

For example:

left_distances  = [2, 3]
right_distances = [1]

This means:

the left subtree contains leaves at distances 2 and 3
the right subtree contains one leaf at distance 1

All distances are measured from the current node.

Step 4: Count valid cross-subtree pairs

Every pair consisting of:

one leaf from the left subtree
one leaf from the right subtree

forms a path passing through the current node.

For every combination:

left_distance + right_distance

If the sum is less than or equal to distance, it is a good pair.

Step 5: Build distances for the parent

The parent needs updated distances.

Every subtree distance increases by 1 because moving upward adds one edge.

So we create:

new_distance = old_distance + 1

We only keep distances strictly smaller than distance, because larger values can never participate in future valid pairs.

Step 6: Return the updated distance list

The recursive function returns the new list upward.

Eventually, the root finishes processing all subtrees and the global answer contains the total number of good pairs.

Why it works

Every pair of leaf nodes has a unique lowest common ancestor. When DFS processes that ancestor, one leaf appears in the left subtree list and the other appears in the right subtree list.

The algorithm checks all such combinations exactly once, so every valid pair is counted once and only once.

The returned distance lists always correctly represent leaf distances from the current node, which preserves correctness throughout recursion.

Python Solution

# 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

from typing import Optional, List

class Solution:
    def countPairs(self, root: Optional[TreeNode], distance: int) -> int:
        good_pairs = 0

        def dfs(node: Optional[TreeNode]) -> List[int]:
            nonlocal good_pairs

            if not node:
                return []

            # Leaf node
            if not node.left and not node.right:
                return [1]

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

            # Count valid pairs
            for left_distance in left_distances:
                for right_distance in right_distances:
                    if left_distance + right_distance <= distance:
                        good_pairs += 1

            # Build distances for parent
            current_distances = []

            for dist in left_distances:
                if dist + 1 < distance:
                    current_distances.append(dist + 1)

            for dist in right_distances:
                if dist + 1 < distance:
                    current_distances.append(dist + 1)

            return current_distances

        dfs(root)

        return good_pairs

The implementation follows the exact recursive strategy described earlier.

The dfs() function returns a list of leaf distances from the current node.

The base cases are:

None node returns an empty list
leaf node returns [1]

For internal nodes, recursion gathers distances from both subtrees.

The nested loops compare every left-subtree leaf against every right-subtree leaf. If their combined path length is within the allowed limit, the global counter increases.

After counting pairs, the function prepares distance values for the parent. Every distance increases by one because the parent is one edge farther away.

Distances that are already too large are discarded early because they can never form a valid future pair.

Finally, the recursion finishes at the root and returns the accumulated answer.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func countPairs(root *TreeNode, distance int) int {
    goodPairs := 0

    var dfs func(node *TreeNode) []int

    dfs = func(node *TreeNode) []int {
        if node == nil {
            return []int{}
        }

        // Leaf node
        if node.Left == nil && node.Right == nil {
            return []int{1}
        }

        leftDistances := dfs(node.Left)
        rightDistances := dfs(node.Right)

        // Count valid pairs
        for _, leftDist := range leftDistances {
            for _, rightDist := range rightDistances {
                if leftDist+rightDist <= distance {
                    goodPairs++
                }
            }
        }

        currentDistances := []int{}

        // Prepare distances for parent
        for _, dist := range leftDistances {
            if dist+1 < distance {
                currentDistances = append(currentDistances, dist+1)
            }
        }

        for _, dist := range rightDistances {
            if dist+1 < distance {
                currentDistances = append(currentDistances, dist+1)
            }
        }

        return currentDistances
    }

    dfs(root)

    return goodPairs
}

The Go implementation mirrors the Python logic closely.

Instead of Python lists, Go uses integer slices. Recursive closures in Go require declaring the function variable first and assigning the implementation afterward.

Nil handling is explicit with node == nil.

Since the constraints are small, standard integer arithmetic is completely safe and no overflow concerns exist.

Worked Examples

Example 1

Input:
root = [1,2,3,null,4]
distance = 3

Tree:

Leaf nodes are:

DFS Traversal

Node	Left Distances	Right Distances	Valid Pairs Added	Returned Distances
4	[]	[]	0	[1]
2	[]	[1]	0	[2]
3	[]	[]	0	[1]
1	[2]	[1]	1	[]

At node 1:

2 + 1 = 3

This satisfies the condition.

Final answer:

Example 2

Input:
root = [1,2,3,4,5,6,7]
distance = 3

Tree:

Leaf nodes:

DFS Processing

Node	Left Distances	Right Distances	Valid Pairs Added
2	[1]	[1]	1
3	[1]	[1]	1
1	[2,2]	[2,2]	0

At node 2:

1 + 1 = 2

Pair (4,5) is valid.

At node 3:

1 + 1 = 2

Pair (6,7) is valid.

At node 1:

2 + 2 = 4

No cross-subtree pairs satisfy the limit.

Final answer:

Example 3

Input:
root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
distance = 3

Tree:

Leaf nodes:

Important Pair Checks

Pair	Distance	Valid
(6,5)	4	No
(6,2)	5	No
(5,2)	3	Yes

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N × D²)	Each node compares at most D distances from each subtree
Space	O(H + D)	Recursion stack plus bounded distance storage

Here:

N is the number of nodes
D is the maximum allowed distance
H is the height of the tree

Because distance <= 10, each subtree stores only a small number of values. The nested comparisons therefore remain very small in practice.

The recursion stack depends on tree height:

balanced tree: O(log N)
skewed tree: O(N)

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Example 1
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.right = TreeNode(4)

assert Solution().countPairs(root1, 3) == 1  # Basic valid pair

# Example 2
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)
root2.left.left = TreeNode(4)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(6)
root2.right.right = TreeNode(7)

assert Solution().countPairs(root2, 3) == 2  # Two sibling leaf pairs

# Example 3
root3 = TreeNode(7)
root3.left = TreeNode(1)
root3.right = TreeNode(4)
root3.left.left = TreeNode(6)
root3.right.left = TreeNode(5)
root3.right.right = TreeNode(3)
root3.right.right.right = TreeNode(2)

assert Solution().countPairs(root3, 3) == 1  # Only one valid pair

# Single node tree
root4 = TreeNode(1)

assert Solution().countPairs(root4, 2) == 0  # No leaf pairs exist

# Two leaves exactly at distance limit
root5 = TreeNode(1)
root5.left = TreeNode(2)
root5.right = TreeNode(3)

assert Solution().countPairs(root5, 2) == 1  # Distance exactly equals limit

# Two leaves beyond limit
root6 = TreeNode(1)
root6.left = TreeNode(2)
root6.right = TreeNode(3)

assert Solution().countPairs(root6, 1) == 0  # Distance exceeds limit

# Skewed tree
root7 = TreeNode(1)
root7.right = TreeNode(2)
root7.right.right = TreeNode(3)
root7.right.right.right = TreeNode(4)

assert Solution().countPairs(root7, 3) == 0  # Only one leaf exists

# Multiple leaves with mixed valid distances
root8 = TreeNode(1)
root8.left = TreeNode(2)
root8.right = TreeNode(3)
root8.left.left = TreeNode(4)
root8.left.right = TreeNode(5)
root8.right.right = TreeNode(6)

assert Solution().countPairs(root8, 3) == 1  # Only (4,5) is valid

Test Summary

Test	Why
Example 1	Validates simple cross-subtree pair
Example 2	Validates multiple good pairs
Example 3	Validates uneven tree structure
Single node tree	Ensures no pair counted
Exact distance limit	Confirms inclusive comparison
Beyond distance limit	Ensures invalid pairs excluded
Skewed tree	Tests recursion on unbalanced tree
Mixed valid distances	Verifies selective counting

Edge Cases

Single Node Tree

A tree containing only one node has exactly one leaf and therefore no possible pair.

This case can easily cause incorrect implementations to accidentally count nonexistent pairs or mishandle recursion.

The implementation handles this naturally because the DFS returns [1] for the single leaf, but no node ever combines left and right subtree distances.

Extremely Skewed Tree

A tree shaped like a linked list contains only one leaf at the deepest level.

Recursive tree algorithms sometimes assume branching exists, which can lead to incorrect pair counting or invalid indexing.

The solution safely handles this because empty subtrees return empty lists, and no cross-subtree comparisons occur.

Distance Exactly Equal to the Limit

The condition is:

distance_between_leaves <= distance

Implementations sometimes mistakenly use a strict inequality.

The solution correctly uses:

if left_distance + right_distance <= distance:

so pairs exactly at the threshold are counted.

Large Distances Propagating Upward

If distances larger than the allowed limit continue propagating upward, unnecessary work accumulates and logic becomes harder to reason about.

The implementation prunes these values early:

if dist + 1 < distance:

This guarantees only potentially useful distances continue through recursion.