Is Number of Good Leaf Nodes Pairs easy or hard?

Number of Good Leaf Nodes Pairs is classified as Medium difficulty. The challenge is recognizing that leaf pairs can be counted while merging subtree distance information during DFS rather than comparing every leaf pair directly.

Number of Good Leaf Nodes Pairs Python/Java solution

Python and Java implementations typically use a recursive DFS that returns an integer array representing leaf counts by distance. During the merge step, nested loops combine distances from left and right children to count valid leaf pairs.

How to solve Number of Good Leaf Nodes Pairs in O(n)?

A near-linear solution uses a single DFS traversal that aggregates leaf distances from subtrees. Each node returns an array of counts for leaves at different depths. While the theoretical complexity is O(n · d²), the small bound on d keeps operations constant per node, making the runtime close to O(n).

What is the best approach for Number of Good Leaf Nodes Pairs?

The most common approach uses DFS with distance arrays. During a postorder traversal, each node returns counts of leaf nodes at different distances in its subtree. When merging left and right children, pairs whose combined distance is ≤ the given limit are counted. This runs in O(n · d²) time where d is the distance limit.

Is Number of Good Leaf Nodes Pairs asked at Google/Amazon/Meta?

Tree traversal and leaf distance aggregation problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test depth-first search, lowest common ancestor reasoning, and dynamic programming on trees.

What data structure is used in Number of Good Leaf Nodes Pairs?

The problem primarily uses a binary tree with depth-first search traversal. During recursion, arrays or small frequency lists track how many leaf nodes appear at each distance from the current node.

What is the time complexity of Number of Good Leaf Nodes Pairs?

The optimal DFS solution runs in O(n · d²) time, where n is the number of nodes and d is the maximum allowed distance between leaves. Since d is typically ≤ 10 in the constraints, the nested distance checks are small constants, making the algorithm effectively linear in practice.

Description Hints 3 Solution Video 20:22

1530. Number of Good Leaf Nodes Pairs

Medium71.9% acceptance3 companies

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 said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: 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
Explanation: 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
Explanation: The only good pair is [2,5].

Constraints:

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

Asked at 3 companies

Tiktok Bytedance

Google

Topics

Hints open one at a time

Hint 1

Start DFS from each leaf node. stop the DFS when the number of steps done > distance.

Hint 2

If you reach another leaf node within distance steps, add 1 to the answer.

Hint 3

Note that all pairs will be counted twice so divide the answer by 2.

20:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def countPairs(self, root: Optional[TreeNode], distance: int) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3,null,4]
3

Input

[1,2,3,4,5,6,7]
3

Input

[7,1,4,6,null,5,3,null,null,null,null,null,2]
3

Your code is saved on this device.Solution