1530. Number of Good Leaf Nodes Pairs

leetcode

Problem:

The problem is to find the number of good leaf node pairs in a binary tree. A pair of leaf nodes (leaf1, leaf2) is considered good if the distance between them is less than or equal to a given value `distance`. The distance between two nodes in a binary tree is the number of edges on the shortest path between them.

Solution Description:

To implement the solution, we need to perform the following steps:

Traverse the tree using a Depth-First Search (DFS) approach.
For each node, collect the distances to all leaf nodes in its subtree.
Combine the distances from the left and right subtrees to count the number of good leaf node pairs.
Propagate the distances up to the root, adjusting for the distance increment as we move up in the tree.
The count of good leaf node pairs is accumulated during the traversal.

Time Complexity: The solution operates in O(n²) for each node combination in the worst case, where n is the number of nodes. Space Complexity: The space complexity is O(n) due to the recursion stack and storage of leaf distances.

Example:

Consider a binary tree:

For `distance = 3`, a possible solution:

Pairs (4, 5) and (4, 6) are within distance 3.
The function should return 2.

Setup:

Introduces the general framework of the solution.

/**
 * Definition for a binary tree node.
 * @param {TreeNode} val
 * @param {TreeNode} left
 * @param {TreeNode} right
 * @constructor
 */
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Main solution function to find the number of good leaf node pairs.
 * @param {TreeNode} root
 * @param {number} distance
 * @return {number}
 */
function numberOfGoodLeafNodePairs(root, distance) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    log(root, distance);
    return 0; // Dummy return
}

// Test cases
const testCases = [
    {
        root: new TreeNode(1, 
            new TreeNode(2, new TreeNode(4)), 
            new TreeNode(3, new TreeNode(5), new TreeNode(6))
        ),
        distance: 3,
        expected: 2
    },
    {
        root: new TreeNode(1, new TreeNode(2), new TreeNode(3)),
        distance: 1,
        expected: 0
    },
    {
        root: new TreeNode(1, new TreeNode(2)), // Single path tree
        distance: 2,
        expected: 0
    },
    {
        root: new TreeNode(1, 
            new TreeNode(2, 
                new TreeNode(4), 
                new TreeNode(5, null, new TreeNode(8))
            ), 
            new TreeNode(3, 
                new TreeNode(6), 
                new TreeNode(7, null, new TreeNode(9))
            )
        ),
        distance: 4,
        expected: 4
    },
    {
        root: new TreeNode(1), // Single node tree
        distance: 1,
        expected: 0
    }
];

testCases.forEach((test, index) => {
    const result = numberOfGoodLeafNodePairs(test.root, test.distance);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});