Number of Good Leaf Nodes Pairs
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.
Approach 1: Graph Conversion + BFS
class Solution {
public int countPairs(TreeNode root, int distance) {
Map> graph = new HashMap<>();
Set leafNodes = new HashSet<>();
traverseTree(root, null, graph, leafNodes);
int ans = 0;
for (TreeNode leaf : leafNodes) {
Queue bfsQueue = new LinkedList<>();
Set seen = new HashSet<>();
bfsQueue.add(leaf);
seen.add(leaf);
// Go through all nodes that are within the given distance of
// the current leaf node
for (int i = 0; i <= distance; i++) {
// Clear all nodes in the queue (distance i away from leaf node)
// Add the nodes' neighbors (distance i+1 away from leaf node)
int size = bfsQueue.size();
for (int j = 0; j < size; j++) {
// If current node is a new leaf node, add the found pair to our count
TreeNode currNode = bfsQueue.remove();
if (leafNodes.contains(currNode) && currNode != leaf) {
ans++;
}
if (graph.containsKey(currNode)) {
for (TreeNode neighbor : graph.get(currNode)) {
if (!seen.contains(neighbor)) {
bfsQueue.add(neighbor);
seen.add(neighbor);
}
}
}
}
}
}
return ans / 2;
}
private void traverseTree(
TreeNode currNode,
TreeNode prevNode,
Map> graph,
Set leafNodes
) {
if (currNode == null) {
return;
}
if (currNode.left == null && currNode.right == null) {
leafNodes.add(currNode);
}
if (prevNode != null) {
graph.computeIfAbsent(prevNode, k -> new ArrayList());
graph.get(prevNode).add(currNode);
graph.computeIfAbsent(currNode, k -> new ArrayList());
graph.get(currNode).add(prevNode);
}
traverseTree(currNode.left, currNode, graph, leafNodes);
traverseTree(currNode.right, currNode, graph, leafNodes);
}
}
Time Complexity: O(n^2) and Space Complexity: O(n)
Number of Good Leaf Nodes Pairs
The problem Number of Good Leaf Nodes Pairs is a challenging binary tree problem. It focuses on identifying pairs of leaf nodes where the sum of distances between them does not exceed a given threshold.
Problem Statement
Given the root of a binary tree and an integer distance, return the number of pairs of leaf nodes such that the sum of the distances between them is less than or equal to distance.
Key points:
- A "leaf node" is a node with no children.
- The "distance" between two nodes is the number of edges on the path connecting them.
Approach to Solve the Problem
The solution involves recursive traversal of the binary tree while maintaining the distances between leaf nodes. We combine results from the left and right subtrees to count valid pairs efficiently.
Steps to Solve:
- Perform a depth-first search (DFS) on the tree.
- At each node, collect the distances of leaf nodes from the current node.
- Combine the leaf distances from the left and right subtrees to count valid pairs.
- Return the total number of good leaf node pairs.
Implementation
Here is the Python implementation:
class Solution:
def countPairs(self, root, distance):
self.result = 0
def dfs(node):
if not node:
return []
if not node.left and not node.right:
return [1]
left_distances = dfs(node.left)
right_distances = dfs(node.right)
# Count good pairs
for l in left_distances:
for r in right_distances:
if l + r <= distance:
self.result += 1
# Increment distances and return
return [d + 1 for d in left_distances + right_distances if d + 1 < distance]
dfs(root)
return self.result
Here is a Java implementation:
class Solution {
private int result = 0;
public int countPairs(TreeNode root, int distance) {
dfs(root, distance);
return result;
}
private List dfs(TreeNode node, int distance) {
if (node == null) return new ArrayList<>();
if (node.left == null && node.right == null) {
List leafDistances = new ArrayList<>();
leafDistances.add(1);
return leafDistances;
}
List leftDistances = dfs(node.left, distance);
List rightDistances = dfs(node.right, distance);
// Count good pairs
for (int l : leftDistances) {
for (int r : rightDistances) {
if (l + r <= distance) result++;
}
}
// Increment distances and return
List newDistances = new ArrayList<>();
for (int d : leftDistances) {
if (d + 1 < distance) newDistances.add(d + 1);
}
for (int d : rightDistances) {
if (d + 1 < distance) newDistances.add(d + 1);
}
return newDistances;
}
}
Example
Consider the binary tree:
Tree Structure:
1
/ \
2 3
/ \ \
4 5 6
With distance = 3:
- Good pairs are: (4, 5), (4, 6), and (5, 6).
- The result is
3.
Complexity Analysis
Time Complexity: O(n²), where n is the number of nodes in the tree. In the worst case, each pair of leaf nodes is checked.
Space Complexity: O(h), where h is the height of the tree. This accounts for the recursive call stack.
Applications
- Used in networking to calculate communication limits between nodes.
- Helps in analyzing distances between nodes in hierarchical systems.
- Applies to graph-based problems with constraints on path lengths.
Conclusion
The problem Number of Good Leaf Nodes Pairs challenges your understanding of binary tree traversal and recursive logic. By carefully combining results from subtrees, it is possible to solve the problem efficiently while adhering to the distance constraint.
Practice similar problems to enhance your problem-solving skills in tree-based algorithms.
