Number of Good Leaf Nodes Pairs in Java
Number of Good Leaf Nodes Pairs in Java
Given the root of a binary tree and an integer distance, a pair of two different leaf nodes of the binary tree is considered "good" if the length of the shortest path between them is less than or equal to the given distance. The task is to return the number of such good leaf node pairs.
Example
![Number of Good Leaf Nodes Pairs in Java](https://static.tutorialandexample.com/java/number-of-good-leaf-nodes-pairs-in-java1.png)
Input: root = [1, 2, 3, 4, None]
distance = 2
Output: 0
Explanation:
The leaf nodes are 4 and 3.
The shortest path between 4 and 3 is 4 -> 2 -> 1 -> 3 with a length of 3.
Since the distance (3) is greater than 2, there are no good pairs.
Depth-First Search (DFS) Approach
Algorithm
Step 1: Initialize counter.
Step 2: Define recursive function returning distance array.
Step 3: Return zero-initialized array if node is null.
Step 4: Return array with distance 1 set to 1 if node is a leaf.
Step 5: Recursively call function for left and right children.
Step 6: Count good pairs using distances from left and right children.
Step 7: Increment distances by 1 for non-leaf nodes.
Step 8: Return updated distances array.
Step 9: Call recursive function with root node.
Step 10: Return final count.
FileName: GoodLeafNode.java
import java.util.*; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class GoodLeafNode { private int count = 0; public int countPairs(TreeNode root, int distance) { dfs(root, distance); return count; } private int[] dfs(TreeNode node, int distance) { if (node == null) { return new int[distance + 1]; } if (node.left == null && node.right == null) { int[] leafDistances = new int[distance + 1]; leafDistances[1] = 1; return leafDistances; } int[] leftDistances = dfs(node.left, distance); int[] rightDistances = dfs(node.right, distance); // Calculate good pairs using left and right distances for (int i = 1; i <= distance; i++) { for (int j = 1; j <= distance; j++) { if (i + j <= distance) { count += leftDistances[i] * rightDistances[j]; } } } int[] distances = new int[distance + 1]; // Increment distances by 1 for non-leaf nodes for (int i = 1; i < distance; i++) { distances[i + 1] = leftDistances[i] + rightDistances[i]; } return distances; } public static void main(String[] args) { GoodLeafNode sol = new GoodLeafNode(); TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); int distance = 2; System.out.println(sol.countPairs(root, distance)); } }
Output:
0
Complexity Analysis: The code has time complexity of O(n*distance^2) and a space complexity of O(n*distance).
Breadth-First Search Approach
Algorithm
Step 1: Initialize queue with root.
Step 2: Initialize good pairs counter.
Step 3: While queue is not empty, process current node.
Step 4: Calculate leaf distances if node has both children.
Step 5: Increment good pairs if distances are valid and within limit.
Step 6: Add children to queue if they exist.
Step 7: Define helper function to find nearest leaf distance.
Step 8: Return total good pairs count.
FileName: GoodLeafNode1.java
import java.util.*; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class GoodLeafNode1 { public int countPairs(TreeNode root, int distance) { if (root == null) { return 0; } Queuequeue = new LinkedList<>(); queue.offer(root); int goodPairs = 0; while (!queue.isEmpty()) { TreeNode current = queue.poll(); // If the current node has both left and right children if (current.left != null && current.right != null) { int leftDistance = getDistanceToLeaf(current.left, 1, distance); int rightDistance = getDistanceToLeaf(current.right, 1, distance); // Check if the sum of distances is within the allowed distance if (leftDistance != -1 && rightDistance != -1 && leftDistance + rightDistance <= distance) { goodPairs++; } } // Add left child to the queue if it exists if (current.left != null) { queue.offer(current.left); } // Add right child to the queue if it exists if (current.right != null) { queue.offer(current.right); } } return goodPairs; } private int getDistanceToLeaf(TreeNode node, int currentDistance, int maxDistance) { if (node == null) { return -1; } if (node.left == null && node.right == null) { return currentDistance; } int leftDistance = getDistanceToLeaf(node.left, currentDistance + 1, maxDistance); int rightDistance = getDistanceToLeaf(node.right, currentDistance + 1, maxDistance); // Return the minimum distance to a leaf from the current node if (leftDistance != -1 && rightDistance != -1) { return Math.min(leftDistance, rightDistance); } else if (leftDistance != -1) { return leftDistance; } else { return rightDistance; } } public static void main(String[] args) { GoodLeafNode1 sol = new GoodLeafNode1(); TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); int distance = 2; System.out.println(sol.countPairs(root, distance)); } }
Output:
0
Complexity Analysis: The code has time complexity of O(n^2) and a space complexity of O(n).