Problem statement

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/

Solution

One idea is to create tree in the way of defaultdict and then run bfs from each node.

Another way is to use dfs(node), where the answer is distances between node and all leafs which can be reached from this node.

Complexity

Time is O(n^2), because we have equation T(n) = 2*T(n//2) + O(n^2). Space can be O(n^2) as well.

Code

class Solution:
    def countPairs(self, root, dist):
        def dfs(node):
            if not node: return []
            if not node.left and not node.right: return [1]

            left = dfs(node.left)
            right = dfs(node.right)
            self.count += sum(l + r <= dist for l in left for r in right)
            return [n + 1 for n in left + right if n + 1 < dist]
        
        self.count = 0
        dfs(root)
        return self.count

Remark

There is also O(n log n) time complexity: maintain the valid distance in sorted order and use two pointers technique (and probaly larger to smaller tecnique?)