Start learning free

LESSON 433 OF 576 · BINARY TREES

Count Good Nodes in a Binary Tree in Rust: O(n) DFS

Practice O(n) Read the full explanation

Given the root of a binary tree, return the number of good nodes in the tree.

A node X is good when no node on the path from the root down to X has a value greater than the value of X.

A node whose value equals the largest value above it is still good, and the root is always good: nothing is above it.

The trees below are written in level order (top to bottom, left to right), with None for a missing child.

 

Example 1:

      3
     / \
    1   4
   /   / \
  3   1   5

Input: root = [3,1,4,3,None,1,5]
Output: 4
Explanation: The good nodes are the root 3, then 4 (path 3 → 4), 5 (path 3 → 4 → 5) and the 3 at the bottom left (path 3 → 1 → 3: nothing on it is greater than 3). The 1 under the root is not good: 3 is greater. Neither is the 1 under 4: 3 and 4 are greater.

Example 2:

      3
     /
    3
   / \
  4   2

Input: root = [3,3,None,4,2]
Output: 3
Explanation: The root 3, the 3 under it (an equal value is not greater) and the 4 are good. The 2 is not: the path 3 → 3 → 2 has greater values.

Example 3:

Input: root = [1]
Output: 1
Explanation: The root is always good.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • Each node value is between -104 and 104.
  • The tree is at most 800 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, visiting each node once.

Walking back up the path from every node would take up to O(n · h) time for a tree h levels deep. Instead, carry what you need down the path as you go.

STEP 1 OF 12
    Ctrl + Enter to check

    RUST · BINARY TREES

    Count Good Nodes In Binary Tree in Rust, explained

    Problem overview

    The function good_nodes receives the root of a binary tree, an Option<Box<TreeNode>>, and returns how many of its nodes are good. A node is good when no node on the path from the root down to it has a greater value. A node equal to the largest value above it is still good, and the root is always good, because nothing is above it. The lesson provides the TreeNode type, with the fields val, left and right, and the tree always has at least one node.

    In the tree [3, 1, 4, 3, None, 1, 5] the answer is 4. The good nodes are the root 3, the 4 (path 3, 4), the 5 (path 3, 4, 5) and the 3 at the bottom left (path 3, 1, 3, where nothing is greater than 3). The 1 under the root is not good, because 3 is greater, and neither is the 1 under the 4.

    In [3, 3, None, 4, 2] the answer is 3. The root 3, the 3 under it (an equal value is not greater) and the 4 are good. The 2 is not, since its path holds two 3s.

    The lesson asks for O(n) time, visiting each node once. Walking back up the path from every node would take up to O(n · h) for a tree h levels deep.

    Approach: carry the largest value down the path

    A node is good exactly when its value is at least the largest value above it. So there is no need to look at the whole path: carry one number down, the largest value seen so far on the path, and compare each node with it. This is a depth-first search with one extra parameter.

    The recursive helper count_good(node, max_so_far) returns the number of good nodes in the tree under node, where max_so_far is the largest value on the path above it. At each node:

    • if node.val >= max_so_far, the node is good and counts 1;
    • the largest value on the path down to this node, itself included, is max_so_far.max(node.val);
    • the answer is this node's count plus the good nodes in the left subtree plus those in the right, both measured against that new largest value.

    Both children get the same new maximum. They share the path down to the current node, and nothing in the left branch lies on the right branch's path.

    The starting value matters. The root is always good, so the search starts from the root's own value. Starting from 0 would be wrong when every value is negative: for the tree with root -5 and children -7 and -3, the correct answer is 2 (the root and the -3), but a search that starts from 0 counts no good nodes and returns 0.

    Step by step

    1. Read the root's value into root_val. The root is an Option, so write root.as_ref().unwrap().val: as_ref looks inside without taking the tree, and unwrap is safe because the tree has a node.
    2. Call the helper with root and root_val as the answer, without a semicolon. The value is read first because passing root moves it into the call.
    3. Declare the helper count_good with the parameters node: Option<Box<TreeNode>> and max_so_far: i32, returning i32.
    4. Make the body a match on node, with no semicolon after it, so its value is what the helper returns.
    5. Base case: the None arm gives 0. An empty tree has no good nodes, and this arm stops the recursion past a leaf.
    6. The node arm: Some(node) binds the box as node, with a block body.
    7. Start a counter: let mut count = 0;. It will hold this node, if good, plus the good nodes below it.
    8. Test the node: if node.val >= max_so_far, set count to 1. Equal counts as good.
    9. Update the maximum: store max_so_far.max(node.val) in new_max.
    10. Add the left subtree: count += Self::count_good(node.left, new_max);
    11. Add the right subtree the same way with node.right.
    12. End the arm with count, without a semicolon, so it is the arm's value.

    The solution in Rust

    impl Solution {
    fn count_good(node: Option<Box<TreeNode>>, max_so_far: i32) -> i32 {
        match node {
            None => 0,
            Some(node) => {
                let mut count = 0;
                if node.val >= max_so_far {
                    count = 1;
                }
                let new_max = max_so_far.max(node.val);
                count += Self::count_good(node.left, new_max);
                count += Self::count_good(node.right, new_max);
                count
            }
        }
    }

    fn good_nodes(root: Option<Box<TreeNode>>) -> i32 {
        let root_val = root.as_ref().unwrap().val;
        Self::count_good(root, root_val)
    }
}

    The Rust details worth a closer look:

    • as_ref() then unwrap(). Calling unwrap() directly on root would move the tree out of the variable. as_ref() turns the Option<Box<TreeNode>> into an Option<&Box<TreeNode>>, so root stays whole. unwrap() would panic on None, but the lesson's trees always have at least one node. Copying val (an i32) out ends the borrow before root is moved on the next line.
    • Moving the subtrees. Self::count_good(node.left, new_max) moves the left subtree into the call, and the same for the right one. Nothing needs them afterwards, so no clone is needed.
    • Shadowing in the match. The pattern Some(node) reuses the name node. Inside the arm it is the Box<TreeNode>, and node.val reads through the box.
    • let mut count = 0; needs mut because the next lines assign to and add to it. The type is inferred as i32 from the function's return type.
    • .max(). a.max(b) returns the larger of two numbers, so new_max is the larger of the old maximum and this node's value.
    • The last expression. count without a semicolon is the arm's value, and the match without a semicolon is the function's value.

    Complexity

    Time: O(n). Each node is visited once, and each visit does a comparison, a max and two calls.

    Space: O(h) for the recursion, where h is the height of the tree. That is about log n for a balanced tree and up to n for a chain. The lesson's trees are at most 800 levels deep, which the recursion handles: a chain of 800 nodes with values decreasing downward returns 1.

    Edge cases and common mistakes

    • One node. [1] returns 1: the root is always good.
    • Negative values. Start from the root's value, not from 0. With root -5 and children -7 and -3, the answer is 2.
    • Equal values. Use >=, not >. In the second example the 3 under the root is good because equal is not greater.
    • Increasing and decreasing chains. A chain 1, 2, 3 going down has three good nodes. A chain 9, 8, 7 has one, the root.
    • Passing the node's value instead of the maximum. A child must be compared with the largest value on the whole path, not only its parent's value. In the first example the 1 under the 4 sits below 3 and 4, so it is not good.
    • Forgetting to update the maximum. If max_so_far were passed down unchanged, every node would be compared only with the root, and a node smaller than a larger value in the middle of its path could wrongly count as good.
    • Reading the root after moving it. Once root is passed to the helper it can't be used again, which is why root_val is read first.

    Testing

    • [3, 1, 4, 3, None, 1, 5] gives 4.
    • [3, 3, None, 4, 2] gives 3.
    • [1] gives 1.
    • Root -5 with children -7 and -3 gives 2.
    • A chain 9, 8, 7 going down gives 1.
    • A chain 1, 2, 3 going down gives 3.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free