Number of Good Leaf Nodes Pairs — Problem & Solution
Number of Good Leaf Nodes Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Good Leaf Nodes Pairs is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree and an integer distance. A pair of two different leaves (nodes with no children) is good if the shortest path between them has at most distance edges.
Return the number of good leaf pairs. Each unordered pair counts once.
Example 1
Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaves 4 and 3 are joined by the path 4-2-1-3 of length 3, which is within the distance.
Example 2
Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The pairs [4,5] and [6,7] are 2 apart; every pair across the root is 4 apart, too far.
Example 3
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: Only the pair [2,5] is close enough (2-3-4-5, length 3).
Constraints
1 <= number of nodes <= 2^101 <= Node.val <= 1001 <= distance <= 10
Hints for Number of Good Leaf Nodes Pairs
Hint 1
The shortest path between two leaves goes up to their lowest common ancestor and back down — so count each pair at that ancestor.
Hint 2
For each node, compute how many leaves of its subtree lie at each depth
1, 2, …, distancebelow it; deeper leaves can never be in a good pair through it or above.Hint 3
At a node, pair every leaf at depth
iin the left subtree with every leaf at depthjin the right subtree wheni + j <= distance. Then shift both lists by one to hand them to the parent.
How to solve Number of Good Leaf Nodes Pairs
Count every good pair at its lowest common ancestor. Each node returns a histogram of its leaves' distances (only up to distance matters), and pairs one side's histogram against the other's.
Approach
walk(node)returns an arraycntwherecnt[d]is the number of leavesdedges belownode, for0 <= d <= distance.- A leaf returns
cnt[0] = 1. - Otherwise get
LandRfrom the children (all zero for a missing child). For everyi,jwith(i + 1) + (j + 1) <= distance, addL[i] · R[j]to the answer. - Return
cnt[d] = L[d - 1] + R[d - 1]ford = 1 … distance.
Why it works
Two leaves in different subtrees of a node have that node as their lowest common ancestor, and their distance is their two depths below it. Every pair of leaves has exactly one lowest common ancestor, where it falls in different subtrees, so every pair is counted exactly once. Leaves deeper than distance below a node cannot form a good pair through it or any ancestor, so the histogram can be cut there.
Complexity
- Time —
O(n · distance^2) - Space —
O(h · distance)
Pitfalls
- Counting a leaf at depth 0 in its own node's pairing step — the leaf's own array only matters to its parent.
- Adding 1 for the edge from each child: the distance between leaves at depths
iandjbelow the children isi + j + 2.
Reference solution
Python
from typing import Optional
def countPairs(root: Optional[TreeNode], distance: int) -> int:
total = 0
def walk(node):
nonlocal total
cnt = [0] * (distance + 1)
if node is None:
return cnt
if node.left is None and node.right is None:
cnt[0] = 1
return cnt
left = walk(node.left)
right = walk(node.right)
for i in range(distance):
if left[i]:
for j in range(distance - 1 - i):
total += left[i] * right[j]
for d in range(1, distance + 1):
cnt[d] = left[d - 1] + right[d - 1]
return cnt
walk(root)
return totalJava
public static int countPairs(TreeNode root, int distance) {
int[] total = new int[1];
pairWalk(root, distance, total);
return total[0];
}
static int[] pairWalk(TreeNode node, int distance, int[] total) {
int[] cnt = new int[distance + 1];
if (node == null) return cnt;
if (node.left == null && node.right == null) { cnt[0] = 1; return cnt; }
int[] left = pairWalk(node.left, distance, total);
int[] right = pairWalk(node.right, distance, total);
for (int i = 0; i < distance; i++)
for (int j = 0; i + j + 2 <= distance; j++) total[0] += left[i] * right[j];
for (int d = 1; d <= distance; d++) cnt[d] = left[d - 1] + right[d - 1];
return cnt;
}C++
vector<int> pairWalk(TreeNode* node, int distance, int& total);
int countPairs(TreeNode* root, int distance) {
int total = 0;
pairWalk(root, distance, total);
return total;
}
vector<int> pairWalk(TreeNode* node, int distance, int& total) {
vector<int> cnt(distance + 1, 0);
if (!node) return cnt;
if (!node->left && !node->right) { cnt[0] = 1; return cnt; }
vector<int> left = pairWalk(node->left, distance, total);
vector<int> right = pairWalk(node->right, distance, total);
for (int i = 0; i < distance; i++)
for (int j = 0; i + j + 2 <= distance; j++) total += left[i] * right[j];
for (int d = 1; d <= distance; d++) cnt[d] = left[d - 1] + right[d - 1];
return cnt;
}JavaScript
var countPairs = function(root, distance) {
var state = { total: 0 };
pairWalk(root, distance, state);
return state.total;
};
var pairWalk = function(node, distance, state) {
var cnt = new Array(distance + 1).fill(0);
if (node === null) return cnt;
if (node.left === null && node.right === null) { cnt[0] = 1; return cnt; }
var left = pairWalk(node.left, distance, state);
var right = pairWalk(node.right, distance, state);
for (var i = 0; i < distance; i++)
for (var j = 0; i + j + 2 <= distance; j++) state.total += left[i] * right[j];
for (var d = 1; d <= distance; d++) cnt[d] = left[d - 1] + right[d - 1];
return cnt;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals