Domain 2MediumMEDIUM

Number of Good Leaf Nodes Pairs

LeetCode problem 1530: Number of Good Leaf Nodes Pairs (medium).

Domain: medium•Updated: 2026-09-18
#Tree#Depth-first Search

Problem Breakdown

We are given a binary tree root and an integer distance. We need to count the number of unique pairs of leaf nodes such that the shortest path between them is less than or equal to distance.

Inputs:

  • root: The head node of a Binary Tree.
  • distance: An integer representing the maximum allowed edge distance between two leaves.

Outputs:

  • A single integer count of valid pairs.

Implicit Constraints & Edge Cases:

  1. Leaf Definition: Only nodes with no children are considered leaf nodes. If the tree has only one node (which is a root and a leaf), there can be zero pairs because we need two different leaves.
  2. Path Calculation: The shortest path between two nodes in a binary tree always passes through their Lowest Common Ancestor (LCA).
  3. Pruning Opportunity: Since distance is small (≤10\le 10), any leaf further than this distance from the current node cannot form a valid pair with leaves passing through ancestors of that node. We can safely discard distances exceeding our limit to keep complexity low.
  4. Empty/Single Node: If there are fewer than two nodes, or only one leaf exists in total (e.g., [1]), output is 0.

Intuition

A brute-force approach would be to collect all leaves first (O(N)O(N)) and then iterate through every pair of leaves to calculate their path length. Calculating the distance between a specific pair requires traversing up from both nodes or using LCA logic, taking O(H)O(H) where HH is height. With potentially many leaf pairs (up to (N/2)2(N/2)^2), this leads to roughly O(N3⋅H)O(N^3 \cdot H) or at best O(N1.5)O(N^{1.5}), which might TLE on larger inputs if not optimized.

Key Insight: We can solve this using a Post-Order DFS traversal. As we return from the recursion, each node returns information about its subtree: specifically, how far down are all leaves in that subtree relative to the current node?

At any internal node u, if it has both left and right children (or valid subtrees), any pair of leaves formed by one leaf from the left side and one from the right side will have their path passing through u. The distance between them is simply (distance_from_left_leaf_to_u) + 1 + (distance_from_right_leaf_to_u).

We can maintain a list of distances to all valid leaves in the current subtree. Since we only care about paths ≤\le distance, any leaf further than distance away from this node cannot contribute to future pairs passing through ancestors, so we prune those entries. This keeps our return lists small (bounded by distance).

Approach

  1. Define a Helper Function: Create a DFS function that returns a list of integers representing the distance from the current node down to every leaf in its subtree.
  2. Base Case - Leaf Node: If the current node has no children, it is a leaf. Return [0] (distance to itself).
  3. Recursive Step: Recursively call DFS on left and right children. Handle None nodes by returning an empty list or skipping them in logic.
  4. Count Pairs at Current Node: Iterate through the distance lists from the left child (left_leaves) and right child (right_leaves). For every pair (d1, d2), check if d1 + d2 + 2 <= distance. If true, increment a global counter (the path goes up to current node: +1+1 edge each side).
  5. Merge Lists: Combine the valid lists from left and right children into one list for the current node return value. Filter out any distances greater than distance - 1 because they cannot form pairs with leaves in other branches passing through ancestors within the limit.
  6. Return Result: The final count is accumulated during traversal.

Complexity Analysis

  • Time Complexity: O(N⋅D2)O(N \cdot D^2) or effectively O(N)O(N). Each node is visited once (NN). At each step, we merge lists of size bounded by distance (since we prune distances > distance). Since max distance is small constant 10, the merging cost per node is negligible.
  • Space Complexity: O(H)O(H) for recursion stack depth where HH is tree height. Additionally space proportional to list sizes returned at each step (D⋅ND \cdot N in worst case without pruning, but effectively bounded by distance due to filtering).

Solution

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

def countPairs(root, distance):
    # Global counter for valid pairs found across the tree
    pair_count = 0
    
    def dfs(node):
        nonlocal pair_count
        
        # If node is None or not a leaf (has children), proceed to recursive step. 
        # However, we need to handle leaves specifically in base case logic below.
        
        if node.left and node.right:
            return []  # Not a leaf
            
        left_leaves = dfs(node.left) if node.left else []
        right_leaves = dfs(node.right) if node.right else []
        
        # If current node is a leaf (both children None), it returns [0] 
        # But we need to handle the case where one child exists but other doesn't.
        # Actually, cleaner logic: Check if leaf first? No, standard pattern handles this naturally.
        # Let's refine base cases inside recursion for clarity in implementation below
        
        return dfs(node)

    def solve(n):
        nonlocal pair_count
        
        # Base case: Leaf node (no children or both None)
        if not n.left and not n.right:
            return [0]  # Distance from this leaf to itself is 0
            
        left_dist = []
        right_dist = []
        
        if n.left:
            left_dist = solve(n.left)
        else:
            # If no left child, we can't form pairs through left side. 
            # But wait, the logic needs to be consistent with pruning.
            pass
            
    # Re-writing for cleaner implementation structure within single function scope
    
    def get_leaves(node):
        nonlocal pair_count
        
        if not node:
            return []
        
        is_leaf = (not node.left and not node.right)
        
        left_res = get_leaves(node.left) if node.left else []
        right_res = get_leaves(node.right) if node.right else []
        
        # If current node is a leaf, it returns [0] to its parent. 
        # But we must handle the case where one side exists and other doesn't (unbalanced).
        # Actually, standard logic: return list of distances from leaves in subtree.
        if not left_res and not right_res:
            return [0]

        valid_left = []
        for d in left_res:
            if d < distance - 1: 
                valid_left.append(d)
        
        # Wait, standard pruning is usually done on the returned list to keep it small.
        # Let's stick to the logic that returns all leaves within range 'distance'.
        
        return []

    def helper(node):
        nonlocal pair_count
        
        if not node:
            return []
            
        left = helper(node.left)
        right = helper(node.right)
        
        is_leaf = (not node.left and not node.right)
        
        # If leaf, we just pass up [0] to parent. 
        # But wait, the logic needs to be: if it's a leaf in this subtree, return 0 distance from here?
        # No, usually helper returns list of distances FROM current node TO leaves IN SUBTREE.
        
        # Correct Logic for Helper returning list of depths:
        left = []
        right = []
        
        if not is_leaf and (node.left or node.right): 
            pass
        
    # Let's write the clean implementation directly in solution block to avoid confusion here.

```python
class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:
        self.count = 0
        
        def dfs(node):
            if not node:
                return []
            
            # If leaf node (no children), it is a source of leaves at depth 0 from itself.
            left_leaves = dfs(node.left) if node.left else []
            right_leaves = dfs(node.right) if node.right else []
            
            # Check for valid pairs formed by combining one leaf from left and one from right
            # The path length is d_left + d_right + 2 (edges up to current node)
            for l in left_leaves:
                for r in right_leaves:
                    if l + r + 2 <= distance:
                        self.count += 1
            
            # Prepare list of distances from this node down to leaves. 
            # We only care about leaves within 'distance' range because any leaf further away
            # cannot form a valid pair with nodes above us (path would exceed limit).
            res = []
            
            if not left_leaves and not right_leaves:
                return [0]  # Current node is a leaf
            
            for d in left_leaves + right_leaves:
                if d < distance - 1: 
                    res.append(d)
                    
            return res

        dfs(root)
        return self.count

Edge Cases Handled

  • Single Node Tree: The dfs returns [0], loops over empty left/right lists, count remains 0. Correct.
  • Distance = 1: Only adjacent leaves (siblings of a parent node). Logic checks l + r + 2 <= 1. Since min d=0d=0, sum is at least 2. Count will be 0 unless distance allows it? Wait, Example 5: [1,1,1], dist=2 -> Output 1 (siblings). If dist=1, siblings are not good because path length between them via parent is 2 edges (L→P→RL \to P \to R). My logic l + r + 2 handles this correctly.
  • Pruning: The code filters distances in the returned list to ensure complexity remains low and avoids counting paths that exceed limits unnecessarily for ancestors.
class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:
        self.count = 0
        
        def dfs(node):
            if not node:
                return []
            
            # Recursively get distances from leaves in left and right subtrees
            left_leaves = dfs(node.left) if node.left else []
            right_leaves = dfs(node.right) if node.right else []
            
            # If current node is a leaf (no children), it contributes distance 0 to its parent.
            # However, we must handle the case where one child exists but not other carefully 
            # by ensuring left/right lists are empty for missing branches.
            
            # Count valid pairs crossing through this node
            if left_leaves and right_leaves:
                for l in left_leaves:
                    for r in right_leaves:
                        if l + r + 2 <= distance:
                            self.count += 1
            
            # Prepare return list. 
            # If current node is a leaf, we only have itself at dist 0 relative to parent?
            # Actually, the logic needs adjustment: 
            # A leaf returns [0]. An internal node merges children's lists and filters by distance-1.
            
            if not left_leaves and not right_leaves:
                return [0]
                
            res = []
            for d in left_leaves + right_leaves:
                if d < distance - 1: 
                    res.append(d)
                    
            return res

        dfs(root)
        return self.count