#1530

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Number of Good Leaf Nodes Pairs

Find the number of good leaf node pairs in a binary tree where the shortest path between them is less than or equal to a given distance.

tree depth first search binary tree

Problem Statement

You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is considered good if the shortest path between them is less than or equal to the given distance.

Your task is to return the number of good leaf node pairs. The tree may contain any number of nodes within the given constraints, and each node has a value between 1 and 100. The maximum distance is 10, and the tree can have up to 210 nodes.

Examples

Example 1

Input: root = [1,2,3,null,4], distance = 3

Output: 1

The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2

Input: root = [1,2,3,4,5,6,7], distance = 3

Output: 2

The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3

Output: 1

The only good pair is [2,5].

Constraints

The number of nodes in the tree is in the range [1, 210].
1 <= Node.val <= 100
1 <= distance <= 10

Solution Approach

Depth-First Search (DFS)

Perform a DFS on the binary tree. Start the DFS from each leaf node and propagate the information of the shortest path distance between the leaf nodes as you go. Keep track of distances to determine if they satisfy the 'good pair' condition.

Pruning DFS for Optimization

In the DFS traversal, prune the search early by terminating the exploration if the distance exceeds the given threshold. This prevents unnecessary computation and optimizes the performance.

Leaf Pair Counting

During the DFS, whenever you find two leaf nodes within the valid distance range, count them as a good pair. Be sure to ensure that leaf nodes are correctly identified, and that pairs are distinct.

Complexity Analysis

Metric	Value
Time	O(N \cdot D)
Space	O(H)

The time complexity of this solution is O(N * D), where N is the number of nodes in the tree and D is the maximum distance. The space complexity is O(H), where H is the height of the tree due to recursion stack space used by DFS.

What Interviewers Usually Probe

Ensure the candidate demonstrates an understanding of DFS traversal and pruning techniques.
Look for clarity in identifying leaf nodes and how they pair within the given distance.
Assess how efficiently the candidate handles the tree structure and memory usage during traversal.

Common Pitfalls or Variants

Common pitfalls

Incorrectly identifying leaf nodes, especially in non-binary trees.
Failing to prune the DFS search when the distance exceeds the threshold, leading to unnecessary computations.
Not handling the edge cases where the tree has only one node or no valid pairs.

Follow-up variants

Modifying the distance threshold dynamically during DFS traversal.
Handling trees with more complex structures such as unbalanced binary trees.
Counting pairs with different criteria, such as considering paths longer than the given distance.

FAQ

What is the best way to identify leaf nodes in this problem?

Leaf nodes are those that have no children. In this problem, identifying them correctly is crucial for counting valid pairs.

What does pruning the DFS mean in this problem?

Pruning the DFS means stopping the search early if the distance exceeds the given threshold, improving the performance of the algorithm.

How does the number of nodes affect the solution's performance?

As the number of nodes increases, the solution’s time complexity increases linearly due to the need to traverse all nodes in the tree. Optimization techniques like pruning are necessary.

How does GhostInterview help with problems like 'Number of Good Leaf Nodes Pairs'?

GhostInterview helps optimize the DFS traversal, ensuring efficient pruning and counting of good pairs, which is crucial for handling larger trees.

What if there are no valid pairs in the tree?

If there are no valid pairs, the correct output is 0, which should be handled gracefully by the DFS traversal.

terminal

Solution

Solution 1: Recursion

The problem asks for the number of good leaf node pairs in a binary tree. The answer can be divided into three parts: the number of good leaf node pairs in the left subtree, the number of good leaf node pairs in the right subtree, and the number of good leaf node pairs formed by leaf nodes from the left subtree and leaf nodes from the right subtree.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

# 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(root, cnt, i):
            if root is None or i >= distance:
                return
            if root.left is None and root.right is None:
                cnt[i] += 1
                return
            dfs(root.left, cnt, i + 1)
            dfs(root.right, cnt, i + 1)

        if root is None:
            return 0
        ans = self.countPairs(root.left, distance) + self.countPairs(
            root.right, distance
        )
        cnt1 = Counter()
        cnt2 = Counter()
        dfs(root.left, cnt1, 1)
        dfs(root.right, cnt2, 1)

        for k1, v1 in cnt1.items():
            for k2, v2 in cnt2.items():
                if k1 + k2 <= distance:
                    ans += v1 * v2
        return ans

Continue Practicing

#1457 pseudo palindromic paths in a binary tree #1448 count good nodes in binary tree #1382 balance a binary search tree