Number of Good Leaf Nodes Pairs

Medium
1952.

Number of Good Leaf Nodes Pairs

Number of Good Leaf Nodes Pairs is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

You are given the root of a binary tree and an integer distance. A pair of two different leaves (nodes with no children) is good if the shortest path between them has at most distance edges.

Return the number of good leaf pairs. Each unordered pair counts once.

Example 1

Input
root = [1,2,3,null,4], distance = 3
Output
1
Explanation
The leaves 4 and 3 are joined by the path 4-2-1-3 of length 3, which is within the distance.

Example 2

Input
root = [1,2,3,4,5,6,7], distance = 3
Output
2
Explanation
The pairs [4,5] and [6,7] are 2 apart; every pair across the root is 4 apart, too far.

Example 3

Input
root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output
1
Explanation
Only the pair [2,5] is close enough (2-3-4-5, length 3).

Constraints

  • 1 <= number of nodes <= 2^10
  • 1 <= Node.val <= 100
  • 1 <= distance <= 10
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} distance
 * @return {number}
 */
var countPairs = function(root, distance) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Good Leaf Nodes Pairs — Problem & Solution

Number of Good Leaf Nodes Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Good Leaf Nodes Pairs is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the root of a binary tree and an integer distance. A pair of two different leaves (nodes with no children) is good if the shortest path between them has at most distance edges.

Return the number of good leaf pairs. Each unordered pair counts once.

Example 1

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaves 4 and 3 are joined by the path 4-2-1-3 of length 3, which is within the distance.

Example 2

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The pairs [4,5] and [6,7] are 2 apart; every pair across the root is 4 apart, too far.

Example 3

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: Only the pair [2,5] is close enough (2-3-4-5, length 3).

Constraints

  • 1 <= number of nodes <= 2^10
  • 1 <= Node.val <= 100
  • 1 <= distance <= 10

Hints for Number of Good Leaf Nodes Pairs

  1. Hint 1

    The shortest path between two leaves goes up to their lowest common ancestor and back down — so count each pair at that ancestor.

  2. Hint 2

    For each node, compute how many leaves of its subtree lie at each depth 1, 2, …, distance below it; deeper leaves can never be in a good pair through it or above.

  3. Hint 3

    At a node, pair every leaf at depth i in the left subtree with every leaf at depth j in the right subtree when i + j <= distance. Then shift both lists by one to hand them to the parent.

How to solve Number of Good Leaf Nodes Pairs

Count every good pair at its lowest common ancestor. Each node returns a histogram of its leaves' distances (only up to distance matters), and pairs one side's histogram against the other's.

Approach

  1. walk(node) returns an array cnt where cnt[d] is the number of leaves d edges below node, for 0 <= d <= distance.
  2. A leaf returns cnt[0] = 1.
  3. Otherwise get L and R from the children (all zero for a missing child). For every i, j with (i + 1) + (j + 1) <= distance, add L[i] · R[j] to the answer.
  4. Return cnt[d] = L[d - 1] + R[d - 1] for d = 1 … distance.

Why it works

Two leaves in different subtrees of a node have that node as their lowest common ancestor, and their distance is their two depths below it. Every pair of leaves has exactly one lowest common ancestor, where it falls in different subtrees, so every pair is counted exactly once. Leaves deeper than distance below a node cannot form a good pair through it or any ancestor, so the histogram can be cut there.

Complexity

  • Time — O(n · distance^2)
  • Space — O(h · distance)

Pitfalls

  • Counting a leaf at depth 0 in its own node's pairing step — the leaf's own array only matters to its parent.
  • Adding 1 for the edge from each child: the distance between leaves at depths i and j below the children is i + j + 2.

Reference solution

Python

from typing import Optional

def countPairs(root: Optional[TreeNode], distance: int) -> int:
    total = 0

    def walk(node):
        nonlocal total
        cnt = [0] * (distance + 1)
        if node is None:
            return cnt
        if node.left is None and node.right is None:
            cnt[0] = 1
            return cnt
        left = walk(node.left)
        right = walk(node.right)
        for i in range(distance):
            if left[i]:
                for j in range(distance - 1 - i):
                    total += left[i] * right[j]
        for d in range(1, distance + 1):
            cnt[d] = left[d - 1] + right[d - 1]
        return cnt

    walk(root)
    return total

Java

public static int countPairs(TreeNode root, int distance) {
    int[] total = new int[1];
    pairWalk(root, distance, total);
    return total[0];
}

static int[] pairWalk(TreeNode node, int distance, int[] total) {
    int[] cnt = new int[distance + 1];
    if (node == null) return cnt;
    if (node.left == null && node.right == null) { cnt[0] = 1; return cnt; }
    int[] left = pairWalk(node.left, distance, total);
    int[] right = pairWalk(node.right, distance, total);
    for (int i = 0; i < distance; i++)
        for (int j = 0; i + j + 2 <= distance; j++) total[0] += left[i] * right[j];
    for (int d = 1; d <= distance; d++) cnt[d] = left[d - 1] + right[d - 1];
    return cnt;
}

C++

vector<int> pairWalk(TreeNode* node, int distance, int& total);

int countPairs(TreeNode* root, int distance) {
    int total = 0;
    pairWalk(root, distance, total);
    return total;
}

vector<int> pairWalk(TreeNode* node, int distance, int& total) {
    vector<int> cnt(distance + 1, 0);
    if (!node) return cnt;
    if (!node->left && !node->right) { cnt[0] = 1; return cnt; }
    vector<int> left = pairWalk(node->left, distance, total);
    vector<int> right = pairWalk(node->right, distance, total);
    for (int i = 0; i < distance; i++)
        for (int j = 0; i + j + 2 <= distance; j++) total += left[i] * right[j];
    for (int d = 1; d <= distance; d++) cnt[d] = left[d - 1] + right[d - 1];
    return cnt;
}

JavaScript

var countPairs = function(root, distance) {
    var state = { total: 0 };
    pairWalk(root, distance, state);
    return state.total;
};

var pairWalk = function(node, distance, state) {
    var cnt = new Array(distance + 1).fill(0);
    if (node === null) return cnt;
    if (node.left === null && node.right === null) { cnt[0] = 1; return cnt; }
    var left = pairWalk(node.left, distance, state);
    var right = pairWalk(node.right, distance, state);
    for (var i = 0; i < distance; i++)
        for (var j = 0; i + j + 2 <= distance; j++) state.total += left[i] * right[j];
    for (var d = 1; d <= distance; d++) cnt[d] = left[d - 1] + right[d - 1];
    return cnt;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals