Number of Good Leaf Nodes Pairs

Leetcode Problem:

• Number of Good Leaf Nodes Pairs

Summary

• The problem is to find the number of good leaf node pairs in a binary tree where a pair of two different leaf nodes is said to be good if the length of the shortest path between them is less than or equal to a given distance.

Approach

• The approach used is to perform a depth-first traversal of the binary tree and store the distances of the leaf nodes in a vector
• Then, for each pair of leaf nodes, check if the distance between them is less than or equal to the given distance
• If it is, increment the count of good pairs.

Complexity

• O(n log n) due to the sorting of the vector of leaf node distances, where n is the number of nodes in the tree.

Explain

• The solution code defines a class Solution with a method countPairs that takes the root of a binary tree and an integer distance as input
• It initializes a variable dist to store the distance and a variable ans to store the count of good pairs
• The method traversal is a helper function that performs a depth-first traversal of the binary tree and stores the distances of the leaf nodes in a vector
• The method countPairs calls the traversal method and initializes the variable dist
• It then calls the traversal method and checks for each pair of leaf nodes if the distance between them is less than or equal to the given distance
• If it is, it increments the count of good pairs
• Finally, it returns the count of good pairs.

Solution Code:

/**
 * 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 dist;
    int ans = 0;
    vector traversal(TreeNode* node){
        if (node->left == nullptr && node->right == nullptr) return {1};
        vector v;
        if (node->left){
            v = traversal(node->left);
        }
        if (node->right){
            vector tmp = traversal(node->right);
            for(int i = 0 ; i < tmp.size(); i++){
                for(int j = 0 ; j < v.size(); j++){
                    if (v[j] + tmp[i] <= dist){
                        ans++;
                    }
                }
            }
            v.insert(v.end(), tmp.begin(), tmp.end());
            
        }
        for(int i = 0 ; i < v.size(); i++){
            v[i] += 1;
        }
        return v;
    }
    int countPairs(TreeNode* root, int distance) {
        dist = distance;
        traversal(root);
        return ans;
    }
};