**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.

## Problem Analysis

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.

## Implementation Strategy

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**.

- Increment the total pair count by
- Add
**depthPlus**to**totalDepthMap**and set the value to**count**plus its existing value.

- Set
- 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.

## Additional Resources

The links below outline some of the points discussed above in more detail.

- Introduction to Graph Traversal Algorithms
- Introduction to Hash Tables
- Introduction to Binary Search Trees: tree maps use binary search trees internally to keep the keys sorted.

### Full Code

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.