Number of good leaf nodes pairs

Tree Depth-First Search Binary Tree

71.8% acceptance

Feb 27, 2026

2500

111

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn count_pairs(root: Option<Rc<RefCell<TreeNode>>>, distance: i32) -> i32 {
    let mut ans = 0;
    Self::dfs(&root, distance, &mut ans);
    ans
  }

  // Returns vec of distances from this node to each leaf in subtree (length 1-based)
  fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, distance: i32, ans: &mut i32) -> Vec<i32> {
    match node {
      None => vec![],
      Some(n) => {
        let b = n.borrow();
        if b.left.is_none() && b.right.is_none() {
          return vec![1]; // leaf at distance 1 from self
        }
        let left_dists = Self::dfs(&b.left, distance, ans);
        let right_dists = Self::dfs(&b.right, distance, ans);
        // Count pairs
        for &l in &left_dists {
          for &r in &right_dists {
            if l + r <= distance {
              *ans += 1;
            }
          }
        }
        // Return distances incremented by 1
        left_dists.into_iter().chain(right_dists)
          .map(|d| d + 1)
          .filter(|&d| d <= distance)
          .collect()
      }
    }
  }
}