This is our solution and implementation to problem #1530: Number of Good Leaf Nodes Pairs on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Number of Good Leaf Nodes Pairs on LeetCode.
We are given the root a binary tree of arbitrary size and an int distance. We define a pair of leaf nodes as good if the path between them is less than or equal to distance. We need to implement an algorithm to count the number of such pairs in any given binary tree. Note that the path is from a leaf to another leaf and a path does not necessarily need to move through the root of the entire tree. However, all paths will need to move up, reach some node, then move down. A path also cannot back track on itself or traverse an edge more than once. In other words, there is no direct sibling traversal, and since this is a tree and not a graph, we must move up, then down, and once we switch we cannot switch again. With this in mind, we can consider the problem as follows:
- For each node:
- Count the number of pairs from this node's left subtree to this node's right subtree.
- Count the pairs from right to left.
- Propagate the total number of leaf nodes and their depths back to the calling method.
We will perform a recursive depth first search and count the number of pairs we find during each traversal. We will also keep track of the depths of each leaf node and how many leaf nodes there are for each depth value. For each recursive call, we'll determine the depth counts on each subtree, left and right, and check for the complimentary values for each on the opposite subtree. At each node, our recursive method will:
- Initialize a Map totalDepthMap to record the depths and counts of each leaf node from the root provided to the method.
- If root is null, return that empty map immediately and do not proceed.
- Create a Map leftDepthMap, recursively call this method on root.left, and assign the result.
- Create a Map rightDepthMap, recursively call this method on root.right, and assign the result.
- Create a Set rightExcludeValues. This will help prevent counting pairs twice later on.
- For each depth and count in leftDepthMap:
- Set depthPlus to depth + 1 for convenience later on.
- Calculate the compliment as distance - depthPlus.
- Iterate over all values in rightMap between 0 and compliment - 1. For each rightKey and rightValue:
- Increment the total pair count by rightValue⋅count.
- Add rightKey to rightExcludeValues.
- Add depthPlus to totalDepthMap and set the value to count plus its existing value.
- For each depth and count in rightDepthMap, do the same for all keys which do not exist in rightExcludeValues.
- If this is a leaf node, put 0, 1 in totalDepthMap.
- Return totalDepthMap.
For convenience, we'll keep track of the total pair count as an instance property. For performance, we'll use a TreeMap, which is a map where they keys are sorted. This will make getting the submap take O(log n) time instead of O(n) time.
Space and Time Complexity
The space complexity is O(n⋅log(n)), as we'll need to keep track of log(n) methods on the call stack, and for each call, keep track of the depth of each leaf node, where there are up to n/2 leaf nodes. The time complexity is O(n^2⋅log(n)), as we'll need to iterate over each node, and for each node, iterate over the compliment submaps to update the pair counts and iterate over the full maps themselves to copy the values.
The links below outline some of the points discussed above in more detail.
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution. Other files are used as utilities to support the main implementation.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.