Problem Description

The problem asks to find the number of good leaf node pairs in a given binary tree. A good pair is defined as a pair of distinct leaf nodes where the shortest path between them is less than or equal to a given distance distance.

Approach

The solution uses a depth-first search (DFS) approach to traverse the binary tree. The key idea is to count the number of leaf nodes at each depth for the left and right subtrees separately. Then, we iterate through the leaf node counts at different depths and calculate the number of good pairs based on the condition that the sum of their depths should be less than or equal to the given distance.

Detailed Explanation with Code (Python)

The Python code below implements this approach:

from collections import Counter
 
# 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(node, depth, counts):
            if not node:
                return
            if not node.left and not node.right:  # Leaf node
                counts[depth] += 1
                return
            dfs(node.left, depth + 1, counts)
            dfs(node.right, depth + 1, counts)
 
        count_left = Counter()
        count_right = Counter()
 
        dfs(root.left, 1, count_left) #depth starts from 1
        dfs(root.right, 1, count_right)
 
        ans = 0
        for d1 in count_left:
            for d2 in count_right:
                if d1 + d2 <= distance:
                    ans += count_left[d1] * count_right[d2]
 
        return ans + self.countPairs(root.left,distance) + self.countPairs(root.right,distance)
 

Explanation:

1. TreeNode class: A simple definition for a tree node.

2. countPairs(root, distance): This is the main function. It recursively calls itself on the left and right subtrees to count pairs within those subtrees. It then focuses on pairs spanning the left and right subtrees of the current node.

3. dfs(node, depth, counts): This is a helper function that performs a depth-first search. It takes the current node, the current depth, and a Counter object to store the counts of leaf nodes at each depth. If a leaf node is encountered, it increments the count for that depth.

4. Counting pairs: After the DFS calls for left and right subtrees, it iterates through the Counter objects (count_left and count_right). For each pair of depths (d1, d2), if their sum is less than or equal to distance, it adds the product of the counts at those depths to the total count (ans). This accounts for all pairs of leaf nodes spanning across the left and right subtrees.

5. Recursive calls: Finally, the function recursively calls itself on the left and right subtrees to handle pairs within those subtrees.

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because the DFS visits each node once.

• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack and the space used by the Counter objects, which store counts for at most H depths. In the worst case (a skewed tree), H can be equal to N.

Other Languages

The code is provided in Python, Java, C++, Go, Typescript, and Javascript, all implementing the same core logic, with minor syntax adjustments for each language. The complexity analysis remains the same across all languages.