Maximum average subtree

Tree Depth-First Search Binary Tree

66.9% acceptance

Mar 31, 2026

858

Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted. A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
  pub fn maximum_average_subtree(root: Option<Rc<RefCell<TreeNode>>>) -> f64 {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, max_avg: &mut f64) -> (i64, i64) {
      if let Some(n) = node {
        let n = n.borrow();
        let (ls, lc) = dfs(&n.left, max_avg);
        let (rs, rc) = dfs(&n.right, max_avg);
        let sum = ls + rs + n.val as i64;
        let count = lc + rc + 1;
        let avg = sum as f64 / count as f64;
        if avg > *max_avg {
          *max_avg = avg;
        }
        (sum, count)
      } else {
        (0, 0)
      }
    }
    let mut max_avg = f64::MIN;
    dfs(&root, &mut max_avg);
    max_avg
  }
}