How hard is LeetCode 1530. Number of Good Leaf Nodes Pairs?

LeetCode 1530. Number of Good Leaf Nodes Pairs is rated Medium on LeetCode.

What is the time complexity of LeetCode 1530. Number of Good Leaf Nodes Pairs?

The Python solution on this page runs in O(n \times d^2 \times h), where n is the number of nodes in the binary tree, and h and d are the height of the binary tree and the distance limit, respectively.

What is the space complexity of LeetCode 1530. Number of Good Leaf Nodes Pairs?

The Python solution on this page uses O(h) for the recursion stack auxiliary space.

What topics does LeetCode 1530. Number of Good Leaf Nodes Pairs cover?

LeetCode 1530. Number of Good Leaf Nodes Pairs is tagged Tree, Depth-First Search and Binary Tree on LeetCode.

Number of Good Leaf Nodes Pairs — LeetCode 1530 Python Solution

MediumTreeDepth-First SearchBinary Tree

Problem: #1530
Pattern: Tree Traversal
Reading time: 6 min
Source: leetcode.com

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

Example

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:
        def dfs(root, cnt, i):
            if root is None or i >= distance:
                return
            if root.left is None and root.right is None:
                cnt[i] += 1
                return
            dfs(root.left, cnt, i + 1)
            dfs(root.right, cnt, i + 1)

        if root is None:
            return 0
        ans = self.countPairs(root.left, distance) + self.countPairs(
            root.right, distance
        )
        cnt1 = Counter()
        cnt2 = Counter()
        dfs(root.left, cnt1, 1)
        dfs(root.right, cnt2, 1)

        for k1, v1 in cnt1.items():
            for k2, v2 in cnt2.items():
                if k1 + k2 <= distance:
                    ans += v1 * v2
        return ans

Complexity

Measure	Complexity
Time	O(n \times d^2 \times h), where n is the number of nodes in the binary tree, and h and d are the height of the binary tree and the distance limit, respectively
Space	O(h) for the recursion stack auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1530. Number of Good Leaf Nodes Pairs is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1530. Number of Good Leaf Nodes Pairs?: LeetCode 1530. Number of Good Leaf Nodes Pairs is rated Medium on LeetCode.
What is the time complexity of LeetCode 1530. Number of Good Leaf Nodes Pairs?: The Python solution on this page runs in O(n \times d^2 \times h), where n is the number of nodes in the binary tree, and h and d are the height of the binary tree and the distance limit, respectively.
What is the space complexity of LeetCode 1530. Number of Good Leaf Nodes Pairs?: The Python solution on this page uses O(h) for the recursion stack auxiliary space.
What topics does LeetCode 1530. Number of Good Leaf Nodes Pairs cover?: LeetCode 1530. Number of Good Leaf Nodes Pairs is tagged Tree, Depth-First Search and Binary Tree on LeetCode.