Practice/LinkedIn/Leetcode 1530. Number of Good Leaf Nodes Pairs

Leetcode 1530. Number of Good Leaf Nodes Pairs

CodingOptional

Problem

Given the root of a binary tree and an integer distance, determine how many distinct pairs of leaf nodes exist where the path length between them is at most distance.

A leaf node is defined as a node with no children. The path between two leaf nodes is the shortest route through their lowest common ancestor. Each edge in the tree contributes 1 to the path length.

Your task is to efficiently count these pairs without explicitly checking every possible leaf pair combination.

Requirements

1. Implement a function that counts valid leaf node pairs
2. A valid pair consists of two distinct leaf nodes
3. The shortest path between the leaves must not exceed the given distance
4. The path length is measured as the number of edges traversed
5. Return the total count of valid pairs

Constraints

• The number of nodes in the tree is in the range [1, 2^10]
• 1 ≤ distance ≤ 10
• Each node value is unique
• The tree may be unbalanced

Examples

Example 1:

` Input: root = [1,2,3,null,4], distance = 3 Output: 1 Explanation: Tree structure: 1 /
2 3
4

The only leaf nodes are 4 and 3. Path from 4 to 3: 4 → 2 → 1 → 3 (length = 3) Since 3 ≤ 3, this pair counts. Answer: 1 `

Example 2:

` Input: root = [1,2,3,4,5,6,7], distance = 3 Output: 2 Explanation: Tree structure: 1 /
2 3 / \ /
4 5 6 7

Leaf nodes: 4, 5, 6, 7 Valid pairs:

• (4,5): path 4→2→5 (length 2) ✓
• (6,7): path 6→3→7 (length 2) ✓
• (4,6): path 4→2→1→3→6 (length 4) ✗
• (4,7): path 4→2→1→3→7 (length 4) ✗
• (5,6): path 5→2→1→3→6 (length 4) ✗
• (5,7): path 5→2→1→3→7 (length 4) ✗ Answer: 2 `

Example 3:

Input: root = [1], distance = 1 Output: 0 Explanation: Only one leaf node exists, so no pairs can be formed.