We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Good Leaf Nodes Pairs

Number: 1653

Difficulty: Medium

Paid? No

Companies: TikTok, ByteDance, josh technology, Google

Problem Description

Given a binary tree and an integer distance, count the number of pairs of leaf nodes such that the shortest path between them is less than or equal to distance. A pair is only considered if both nodes are leaves and they are distinct.

Key Insights

  • Use a depth-first search (DFS) to traverse the tree.
  • At each node, gather the distances of leaf nodes from that node.
  • For a non-leaf node, combine the results from the left and right children to count valid leaf pairs.
  • Increment the distance values as you return to parent nodes and discard distances greater than the allowed distance.
  • The efficiency relies on the fact that the maximum distance is small, allowing a simple pairwise combination at each node.

Space and Time Complexity

Time Complexity: O(n * d^2), where n is the number of nodes and d is the given maximum distance. Space Complexity: O(n), for recursive call stack and storing distance lists.

Solution

We use DFS to traverse the tree. For each node:

  1. If it is a leaf, return a list containing a single element 1 (distance from itself to its parent).
  2. If it is an internal node, recursively obtain distance lists from both the left and right children.
  3. For every combination of a distance from the left child and a distance from the right child, check if the sum is less than or equal to the provided distance. If yes, increment the global count.
  4. Prepare a new list of distances for the current node by incrementing all distances from the children by 1, filtering out those that exceed the maximum allowed distance. By aggregating the counts during the DFS, we count all valid pairs of leaf nodes.

Code Solutions

Below are code implementations in multiple languages.

# 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:
        self.count = 0
        
        def dfs(node):
            # Base case: if node is None, return empty list
            if not node:
                return []
            # If node is a leaf, return a list with one distance (1)
            if not node.left and not node.right:
                return [1]
            
            leftDistances = dfs(node.left)
            rightDistances = dfs(node.right)
            
            # Combine distances from left and right to count valid pairs
            for d1 in leftDistances:
                for d2 in rightDistances:
                    if d1 + d2 <= distance:
                        self.count += 1
                        
            # Prepare new list of distances for the current node
            newDistances = []
            for d in leftDistances + rightDistances:
                # Increase distance by 1 for upper level
                if d + 1 <= distance: 
                    newDistances.append(d + 1)
            return newDistances

        dfs(root)
        return self.count
← Back to All Questions