Start learning free

LESSON 429 OF 572 · BINARY TREES

Count Good Nodes in a Binary Tree in C#: O(n) DFS Carrying the Max

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 null for a missing child.

 

Example 1:

      3
     / \
    1   4
   /   / \
  3   1   5

Input: root = [3,1,4,3,null,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,null,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 9
    Ctrl + Enter to check

    C# · BINARY TREES

    Count Good Nodes In Binary Tree in C#, explained

    Problem overview

    The method GoodNodes receives the root of a binary tree (at least one node) and returns how many 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 class, whose nodes have the fields val, left and right.

    In the tree [3, 1, 4, 3, null, 1, 5] the answer is 4. The root 3 is good. The 1 under it is not (3 is greater). The 3 below that 1 is good, because nothing on its path is greater than 3. The 4 is good, the 1 under the 4 is not, and the 5 is good. In [3, 3, null, 4, 2] the answer is 3: the root, the 3 below it (equal is fine) and the 4 are good, and the 2 is not.

    Approach: carry the largest value down the path

    To decide whether a node is good, you need the largest value on the path above it. Walking back up the path from every node would take up to O(n * h) time for a tree h levels deep. Instead, carry that information down as you go: a recursive method receives the largest value seen so far on the path and passes a possibly larger one to its children.

    At each node:

    1. If the node's value is at least maxSoFar, it is good and counts for 1.
    2. Compute newMax, the larger of maxSoFar and the node's value. This is the largest value on the path down to this node, itself included.
    3. Add the good nodes of the left subtree and the right subtree, both counted against newMax. The two children share the path down to this node, and nothing from the left branch is on the right branch's path.

    The root starts with its own value as maxSoFar, so it passes its own test. For the first example, the method visits the nodes in this order:

    node 3, maxSoFar 3: good
node 1, maxSoFar 3: not good
node 3, maxSoFar 3: good
node 4, maxSoFar 3: good
node 1, maxSoFar 4: not good
node 5, maxSoFar 4: good

    Four lines say "good", matching the answer 4.

    Step by step

    1. In GoodNodes, call the helper CountGood on root, with root.val as the largest value so far, and return its answer. Starting from 0 would be wrong: when every value is negative, the root would fail its own test.
    2. Declare CountGood as a public method returning an int, with a TreeNode parameter node and an int parameter maxSoFar. It returns the number of good nodes in the tree under node.
    3. Base case: if node == null, return 0. An empty tree has no good nodes, and this stops the recursion past the leaves.
    4. Declare count as an int starting at 0.
    5. Test this node: if node.val >= maxSoFar, set count to 1. One comparison checks the whole path, because maxSoFar is its largest value. Equal counts as good.
    6. Compute newMax with Math.Max(maxSoFar, node.val).
    7. Add the left subtree: count += CountGood(node.left, newMax).
    8. Add the right subtree the same way, with node.right.
    9. Return count.

    The solution in C#

    class Solution {
    public int CountGood(TreeNode node, int maxSoFar) {
        if (node == null) {
            return 0;
        }
        int count = 0;
        if (node.val >= maxSoFar) {
            count = 1;
        }
        int newMax = Math.Max(maxSoFar, node.val);
        count += CountGood(node.left, newMax);
        count += CountGood(node.right, newMax);
        return count;
    }

    public int GoodNodes(TreeNode root) {
        return CountGood(root, root.val);
    }
}

    The C# details worth knowing:

    • Values are passed by value. maxSoFar is an int, so each call gets its own copy. When the left call returns, the right call still starts from the same newMax. No "undo" step is needed, as it would be with a shared list or a field.
    • node == null is the check for a missing child. Reading node.val on a null reference would throw a NullReferenceException, so the base case comes first.
    • count += ... adds the right-hand side to the variable and stores it back. It is the same as count = count + ....
    • Math.Max is in the System namespace. In a file of your own, add using System;.
    • Helper before or after. C# lets a method call another written below or above it in the same class. The lesson writes CountGood first just to keep the order of the steps natural.
    • Recursion depth. Each call uses stack space. The tests have at most 800 levels. A chain of 800 nodes, the deepest the tests allow, runs without problems; a much deeper tree could cause a stack overflow, which cannot be caught in C#.

    Complexity

    Time: O(n). Each node is visited once, and the work per node is a comparison, a Math.Max and two calls.

    Space: O(h), where h is the height of the tree, for the recursion. That is about log n for a balanced tree and n for a chain. Nothing else is stored.

    Edge cases and common mistakes

    • One node. [1] gives 1: the root is always good.
    • Negative values. For [-1, -5, -2] the answer is 1: only the root. If the helper started from 0 instead of root.val, the same tree would give 0, and the root would not be counted.
    • Equal values. A tree with three 2s ([2, 2, 2]) gives 3. Using > instead of >= would leave out the equal ones.
    • Decreasing paths. [5, 4, 3, 2] gives 1, only the root. In [-5, -1, -9] the answer is 2: the root and the -1.
    • Increasing paths. [1, 2, 3, 4] gives 4, since every value is at least the maximum above it.
    • Updating maxSoFar before testing the node. If newMax is computed first and used in the test, every node would be compared with a value that already includes itself, and it would look good even when a larger value sits above it.
    • Comparing with the parent only. A node can be larger than its parent and still smaller than a grandparent. The whole path counts, which is why a running maximum is needed, and why the children must receive newMax, not just node.val.

    Testing

    • [3, 1, 4, 3, null, 1, 5] gives 4.
    • [3, 3, null, 4, 2] gives 3.
    • [1] gives 1.
    • [-1, -5, -2] gives 1.
    • [-5, -1, -9] gives 2.
    • [5, 4, 3, 2] gives 1.
    • [1, 2, 3, 4] gives 4.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free