Number of Good Leaf Nodes Pairs
MedPrompt
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
treeis in the range[1, 210]. 1 <= Node.val <= 1001 <= distance <= 10
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is the most straightforward but also the least efficient. It involves three main steps: first, identify all the leaf nodes in the tree. Second, generate all unique pairs of these leaf nodes. Third, for each pair, calculate the shortest path distance between them and check if it's within the given distance.
Algorithm
- Find Leaf Nodes: Traverse the entire tree using a Depth-First Search (DFS) or Breadth-First Search (BFS). If a node has no left and no right child, add it to a list of
leafNodes. - Iterate Through Pairs: Use two nested loops to iterate through all unique pairs of leaf nodes
(leaf1, leaf2)from theleafNodeslist. - Calculate Distance: For each pair, calculate the shortest distance. The shortest path between two nodes in a tree always passes through their Lowest Common Ancestor (LCA). The distance can be calculated as:
distance(leaf1, leaf2) = dist(leaf1, LCA) + dist(leaf2, LCA). This can also be expressed in terms of node depths from the root:depth(leaf1) + depth(leaf2) - 2 * depth(LCA(leaf1, leaf2)). You'll need helper functions to find the LCA of two nodes and to find the distance from an ancestor to a descendant. - Count Good Pairs: If the calculated distance is less than or equal to the given
distance, increment a counter. - Return Count: After checking all pairs, return the final count.
Walkthrough
class Solution { // Finds all leaf nodes and stores them in a list. private void findLeaves(TreeNode node, List<TreeNode> leaves) { if (node == null) return; if (node.left == null && node.right == null) { leaves.add(node); return; } findLeaves(node.left, leaves); findLeaves(node.right, leaves); } // Finds the Lowest Common Ancestor of two nodes. private TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = findLCA(root.left, p, q); TreeNode right = findLCA(root.right, p, q); if (left != null && right != null) return root; return left != null ? left : right; } // Finds the distance from an ancestor to a target node. private int findDistance(TreeNode ancestor, TreeNode target, int depth) { if (ancestor == null) return -1; if (ancestor == target) return depth; int leftDist = findDistance(ancestor.left, target, depth + 1); if (leftDist != -1) return leftDist; return findDistance(ancestor.right, target, depth + 1); } public int countPairs(TreeNode root, int distance) { List<TreeNode> leaves = new ArrayList<>(); findLeaves(root, leaves); int count = 0; for (int i = 0; i < leaves.size(); i++) { for (int j = i + 1; j < leaves.size(); j++) { TreeNode leaf1 = leaves.get(i); TreeNode leaf2 = leaves.get(j); TreeNode lca = findLCA(root, leaf1, leaf2); int dist = findDistance(lca, leaf1, 0) + findDistance(lca, leaf2, 0); if (dist <= distance) { count++; } } } return count; }}Complexity
Time
O(N^2 * H) or O(N^3) in the worst case. Let N be the number of nodes and H be the height. Finding all L leaves takes O(N). There are O(L^2) pairs of leaves. For each pair, finding the LCA takes O(H) and finding distances from LCA takes O(H). Since L can be O(N) and H can be O(N), the total complexity is O(L^2 * H) which simplifies to O(N^3) in the worst-case scenario of a skewed tree.
Space
O(N). We need O(L) space to store the leaf nodes, where L can be O(N). The recursion stack for DFS/LCA can also go up to O(N) in the worst case of a skewed tree.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will likely time out for larger inputs.
Involves multiple traversals of the tree for each pair of leaves.
A more optimized approach involves treating the tree as an undirected graph. We first convert the binary tree into an adjacency list representation. Then, for each leaf node, we perform a Breadth-First Search (BFS) to find all other leaf nodes within the given distance.
Algorithm
- Build Graph and Find Leaves: Traverse the tree once (using DFS). During the traversal, build an adjacency list where each node is connected to its parent and children. Simultaneously, identify and store all leaf nodes in a separate list.
- Iterate and Perform BFS: Iterate through each leaf node in the
leaveslist. - BFS Traversal: For each
startLeaf, initiate a BFS. The BFS explores the graph layer by layer, keeping track of the distance fromstartLeafand a set of visited nodes to avoid redundant computations. - Find Good Pairs: During the BFS, if we encounter another leaf node
endLeafat a distancedsuch thatd <= distance, we've found a good pair. - Count and Avoid Duplicates: Increment a counter for each good pair found. Since this process will find both
(A, B)and(B, A), the final result should be divided by 2.
Walkthrough
class Solution { public int countPairs(TreeNode root, int distance) { Map<TreeNode, List<TreeNode>> graph = new HashMap<>(); List<TreeNode> leaves = new ArrayList<>(); buildGraph(root, null, graph, leaves); int count = 0; for (TreeNode leaf : leaves) { Queue<TreeNode> queue = new LinkedList<>(); Set<TreeNode> visited = new HashSet<>(); queue.add(leaf); visited.add(leaf); for (int level = 0; level <= distance; level++) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode curr = queue.poll(); if (curr != leaf && curr.left == null && curr.right == null) { count++; } if (graph.containsKey(curr)) { for (TreeNode neighbor : graph.get(curr)) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.add(neighbor); } } } } } } return count / 2; } private void buildGraph(TreeNode node, TreeNode parent, Map<TreeNode, List<TreeNode>> graph, List<TreeNode> leaves) { if (node == null) return; if (node.left == null && node.right == null) { leaves.add(node); } graph.putIfAbsent(node, new ArrayList<>()); if (parent != null) { graph.get(node).add(parent); graph.putIfAbsent(parent, new ArrayList<>()); graph.get(parent).add(node); } buildGraph(node.left, node, graph, leaves); buildGraph(node.right, node, graph, leaves); }}Complexity
Time
O(N*L), where N is the number of nodes and L is the number of leaves. Building the graph and finding L leaves takes O(N). Then, we perform a BFS from each of the L leaf nodes. Each BFS can take up to O(N) time as it might traverse the entire graph. Since L can be O(N), the total time is O(L * N) which is O(N^2) in the worst case.
Space
O(N). The adjacency list requires O(N) space. The list of leaves requires O(L) space (where L is the number of leaves). The BFS queue and visited set also require O(N) space in the worst case.
Trade-offs
Pros
More efficient than the brute-force approach.
Correctly models the problem as a shortest path problem on a graph.
Cons
Still potentially too slow if the number of leaves is large.
Requires extra space to build the graph representation.
The most efficient solution uses a single post-order traversal (DFS). For each node, the recursive function calculates the distances to all leaf nodes in its subtree. When returning from the recursive calls for its children, a node can use the lists of leaf distances from its left and right subtrees to count the 'good pairs' that have this node as their lowest common ancestor. The key insight is that the path between a leaf in the left subtree and a leaf in the right subtree must pass through the current node.
Algorithm
- DFS with Return Value: We define a recursive helper function, say
dfs(node), that performs a post-order traversal. This function will return a list of distances fromnodeto each leaf in its subtree. - Base Cases:
- If the current node is
null, return an empty list. - If the current node is a leaf node, return a list containing just the distance
1(representing the distance to its parent).
- If the current node is
- Recursive Step: For an internal node:
- Recursively call
dfson the left child to getleftDistances. - Recursively call
dfson the right child to getrightDistances.
- Recursively call
- Count Pairs: Iterate through all pairs of distances
(d1, d2)whered1is fromleftDistancesandd2is fromrightDistances. The total path length for the corresponding leaves isd1 + d2. Ifd1 + d2 <= distance, increment a global counter. - Propagate Distances Up: Create a new list of distances to return to the parent. For each distance
dinleftDistancesandrightDistances, addd + 1to the new list, but only ifd + 1 < distance. This pruning step is crucial for efficiency, as it keeps the size of the distance lists small. - Return Result: The main function initializes a counter to 0, calls
dfs(root), and returns the final count.
Walkthrough
class Solution { int result = 0; public int countPairs(TreeNode root, int distance) { dfs(root, distance); return result; } private List<Integer> dfs(TreeNode node, int distance) { if (node == null) { return new ArrayList<>(); } if (node.left == null && node.right == null) { List<Integer> leafDist = new ArrayList<>(); leafDist.add(1); return leafDist; } List<Integer> leftDists = dfs(node.left, distance); List<Integer> rightDists = dfs(node.right, distance); // Count pairs with LCA as current node for (int d1 : leftDists) { for (int d2 : rightDists) { if (d1 + d2 <= distance) { result++; } } } // Prepare distances for the parent node List<Integer> parentDists = new ArrayList<>(); for (int d : leftDists) { if (d + 1 < distance) { // Pruning parentDists.add(d + 1); } } for (int d : rightDists) { if (d + 1 < distance) { // Pruning parentDists.add(d + 1); } } return parentDists; }}Complexity
Time
O(N * D^2), where N is the number of nodes and D is the `distance`. We visit each node once. At each node, we process two lists of distances from its children. Due to the pruning (`d + 1 < distance`), the size of these lists is at most D. The nested loop to count pairs takes O(D^2) time. Thus, the total time is O(N * D^2).
Space
O(N * D). The recursion depth can be up to N (the height of the tree). At each level of the recursion, we store a list of distances of size at most D. In the worst case of a skewed tree, this leads to a space complexity of O(N * D).
Trade-offs
Pros
Most efficient solution, using a single pass over the tree.
Effectively uses the
distanceconstraint to prune the search space and keep intermediate data structures small.
Cons
The logic is more complex to reason about compared to the brute-force approaches.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int countPairs ( TreeNode root , int distance ) { if ( root == null ) { return 0 ; } int ans = countPairs ( root . left , distance ) + countPairs ( root . right , distance ); int [] cnt1 = new int [ distance ]; int [] cnt2 = new int [ distance ]; dfs ( root . left , cnt1 , 1 ); dfs ( root . right , cnt2 , 1 ); for ( int i = 0 ; i < distance ; ++ i ) { for ( int j = 0 ; j < distance ; ++ j ) { if ( i + j <= distance ) { ans += cnt1 [ i ] * cnt2 [ j ]; } } } return ans ; } void dfs ( TreeNode root , int [] cnt , int i ) { if ( root == null || i >= cnt . length ) { return ; } if ( root . left == null && root . right == null ) { ++ cnt [ i ]; return ; } dfs ( root . left , cnt , i + 1 ); dfs ( root . right , cnt , i + 1 ); } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} distance * @return {number} */ var countPairs = function (root, distance) { const pairs = []; const dfs = (node) => { if (!node) return []; if (!node.left && !node.right) return [[node.val, 1]]; const left = dfs(node.left); const right = dfs(node.right); for (const [x, dx] of left) { for (const [y, dy] of right) { if (dx + dy <= distance) { pairs.push([x, y]); } } } const res = []; for (const arr of [left, right]) { for (const x of arr) { if (++x[1] <= distance) res.push(x); } } return res; }; dfs(root); return pairs.length; };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countPairs ( TreeNode * root , int distance ) { if ( ! root ) return 0 ; int ans = countPairs ( root -> left , distance ) + countPairs ( root -> right , distance ); vector < int > cnt1 ( distance ); vector < int > cnt2 ( distance ); dfs ( root -> left , cnt1 , 1 ); dfs ( root -> right , cnt2 , 1 ); for ( int i = 0 ; i < distance ; ++ i ) { for ( int j = 0 ; j < distance ; ++ j ) { if ( i + j <= distance ) { ans += cnt1 [ i ] * cnt2 [ j ]; } } } return ans ; } void dfs ( TreeNode * root , vector < int >& cnt , int i ) { if ( ! root || i >= cnt . size ()) return ; if ( ! root -> left && ! root -> right ) { ++ cnt [ i ]; return ; } dfs ( root -> left , cnt , i + 1 ); dfs ( root -> right , cnt , i + 1 ); } };# 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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.