Number of Good Leaf Nodes Pairs - Practice Coding Problems

Number of Good Leaf Nodes Pairs - Problem

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.

Input & Output

Example 1 — Basic Tree

$ Input: root = [1,2,3,null,4], distance = 3

› Output: 1

💡 Note: The only leaf nodes are 3 and 4. The path between them is 3→1→2→4 with length 3, which equals the distance limit of 3.

Example 2 — Multiple Leaves

$ Input: root = [1,2,3,4,5,6,7], distance = 3

› Output: 2

💡 Note: The leaf nodes are 4,5,6,7. Good pairs are (4,5) with distance 2, and (6,7) with distance 2. Other pairs exceed distance 3.

Example 3 — Single Leaf

$ Input: root = [1], distance = 1

› Output: 0

💡 Note: Only one leaf node exists, so no pairs can be formed.

Constraints

The number of nodes in the tree is in the range [1, 2¹⁰].
1 ≤ Node.val ≤ 100
1 ≤ distance ≤ 10

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with leaf nodes and distance limit

Find Leaf Pairs

Calculate shortest path between every pair of leaves

Count Valid Pairs

Count pairs where path length ≤ distance limit

Key Takeaway

🎯 Key Insight: Use DFS to collect leaf distances and count pairs efficiently in a single tree traversal

Asked in

A Amazon 15 G Google 12 M Microsoft 8 F Facebook 6

The key insight is to use DFS to collect distances from each node to leaves in its subtree. The optimal approach uses a single DFS pass with distance propagation: at each node, count valid pairs crossing that node and return incremented distances to parent. Time: O(n × distance²), Space: O(h × distance).

Common Approaches

Approach	Time	Space	Notes
✓ Find All Leaves + Path Calculation	O(n²)	O(n)	Find all leaf nodes, then calculate path distance between every pair
DFS with Distance Propagation	O(n × distance²)	O(h × distance)	Single DFS pass collecting distances from each node to leaves in its subtree

Find All Leaves + Path Calculation — Algorithm Steps

Step 1: DFS to collect all leaf nodes and their paths from root
Step 2: For each pair of leaves, find lowest common ancestor
Step 3: Calculate distance as sum of distances from LCA to both leaves
Step 4: Count pairs where distance ≤ given distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Leaves

DFS to collect all leaf nodes with their paths

Calculate Distances

For each pair, find LCA and compute path distance

Count Valid Pairs

Count pairs where distance ≤ given limit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

typedef struct {
    char* path;
    int len;
} LeafPath;

LeafPath leaves[1000];
int leafCount = 0;

void findLeaves(struct TreeNode* node, char* path, int depth) {
    if (!node) return;
    if (!node->left && !node->right) {
        leaves[leafCount].path = (char*)malloc((depth + 1) * sizeof(char));
        strncpy(leaves[leafCount].path, path, depth);
        leaves[leafCount].path[depth] = '\0';
        leaves[leafCount].len = depth;
        leafCount++;
        return;
    }
    
    if (node->left) {
        path[depth] = 'L';
        findLeaves(node->left, path, depth + 1);
    }
    
    if (node->right) {
        path[depth] = 'R';
        findLeaves(node->right, path, depth + 1);
    }
}

int solution(struct TreeNode* root, int distance) {
    if (!root) return 0;
    
    leafCount = 0;
    char path[1000];
    findLeaves(root, path, 0);
    
    int count = 0;
    for (int i = 0; i < leafCount; i++) {
        for (int j = i + 1; j < leafCount; j++) {
            LeafPath* path1 = &leaves[i];
            LeafPath* path2 = &leaves[j];
            
            int lcaDepth = 0;
            while (lcaDepth < path1->len && lcaDepth < path2->len && 
                   path1->path[lcaDepth] == path2->path[lcaDepth]) {
                lcaDepth++;
            }
            
            int dist = (path1->len - lcaDepth) + (path2->len - lcaDepth);
            if (dist <= distance) {
                count++;
            }
        }
    }
    
    return count;
}

struct TreeNode* buildSimpleTree() {
    // For demo: [1,2,3,null,4]
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->right = createNode(4);
    return root;
}

int main() {
    // Simplified for demo
    struct TreeNode* root = buildSimpleTree();
    int distance = 3;
    
    int result = solution(root, distance);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Finding all leaf pairs O(L²) where L can be O(n), plus LCA calculation

⚠ Quadratic Growth

Space Complexity

O(n)

Storing paths to all leaf nodes and recursion stack

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Find All Leaves + Path Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler