Count good nodes in binary tree

Tree Depth-First Search Breadth-First Search Binary Tree

73.8% acceptance

Feb 25, 2026

6325

212

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X. Return the number of good nodes in the binary tree.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, max_so_far: i32) -> i32 {
      if let Some(n) = node {
        let n = n.borrow();
        let is_good = if n.val >= max_so_far { 1 } else { 0 };
        let new_max = max_so_far.max(n.val);
        is_good + dfs(&n.left, new_max) + dfs(&n.right, new_max)
      } else { 0 }
    }
    dfs(&root, i32::MIN)
  }
}