Number of Good Leaf Nodes Pairs

Number of Good Leaf Nodes Pairs

What is this problem about?

The Number of Good Leaf Nodes Pairs problem gives you a binary tree and an integer distance. A pair of leaf nodes is "good" if the shortest path between them (through the tree) has length ≤ distance. Count all good leaf node pairs. This coding problem uses DFS that returns distance distributions from each subtree's leaves.

Why is this asked in interviews?

ByteDance, TikTok, and Google ask this because it requires a post-order DFS where each node collects distance distributions from its left and right subtrees, then merges them to count pairs. The DFS, binary tree, and tree interview pattern is the core, and the distance distribution propagation is the key technique.

Algorithmic pattern used

Post-order DFS with distance list return. For each node, the DFS returns a list of distances from the current node to all leaf nodes in its subtree. For each pair (left_dist, right_dist) where left_dist + right_dist ≤ distance, count one good pair. Return the incremented distance list to the parent (add 1 to each returned distance, pruning those > distance).

Example explanation

Tree: root→(left→(leaf1, leaf2), right→leaf3). distance=3.

• DFS(leaf1): returns [1] (distance 1 to itself as leaf).
• DFS(leaf2): returns [1].
• DFS(left): merge left_list=[1] and right_list=[1]. 1+1=2≤3 → count 1. Return [2,2] (each leaf is 2 from parent).
• DFS(leaf3): returns [1].
• DFS(root): merge [2,2] and [1]. 2+1=3≤3 (2 pairs). Return pruned list. Total = 3 pairs.

Common mistakes candidates make

• Not pruning distances > distance (causes unnecessary list growth).
• Confusing path length (edges between two leaves through LCA) with depth.
• Using DFS that returns depth instead of distance list (loses distribution information).
• Counting the same pair twice (each pair is counted exactly once at their LCA).

Interview preparation tip

Tree problems where you count pairs satisfying a path-length constraint use the "LCA counting" pattern: count at each internal node the pairs whose path goes through this node (one leaf in left subtree, one in right). The DFS returns a list of leaf-to-node distances. Merging two lists with a pair-count step is O(distance²) per node but bounded by the distance parameter. Practice "count leaf pairs within distance d" and "diameter of binary tree" — they use the same distribute-and-merge pattern.