Count nodes equal to average of subtree

Tree Depth-First Search Binary Tree

86.8% acceptance

Feb 25, 2026

2354

Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree. Note: The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer. A subtree of root is a tree consisting of root and all of its descendants.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn average_of_subtree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, count: &mut i32) -> (i32, i32) {
      if let Some(n) = node {
        let n = n.borrow();
        let (ls, lc) = dfs(&n.left, count);
        let (rs, rc) = dfs(&n.right, count);
        let sum = n.val + ls + rs;
        let cnt = 1 + lc + rc;
        if n.val == sum / cnt {
          *count += 1;
        }
        (sum, cnt)
      } else {
        (0, 0)
      }
    }
    let mut count = 0;
    dfs(&root, &mut count);
    count
  }
}