Start learning free

LESSON 430 OF 573 · BINARY TREES

Count Good Nodes in a Binary Tree in Scala: O(n) Depth-First Search

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

    SCALA · BINARY TREES

    Count Good Nodes In Binary Tree in Scala, explained

    Problem overview

    The method goodNodes receives the root of a binary tree with at least one node 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 class, with an Int field value and the fields left and right, which are null for a missing child.

    In the tree [3, 1, 4, 3, null, 1, 5] (level order, null for a missing child) the answer is 4. The good nodes are the root 3, the 4, the 5 under it, and the 3 at the bottom left, whose path 3, 1, 3 holds nothing greater than 3. The 1 under the root is not good, since 3 is greater, and neither is the 1 under the 4.

    In [3, 3, null, 4, 2] the answer is 3: the root 3, the 3 under it (an equal value is not greater) and the 4 are good, but the 2 is not, because its path 3, 3, 2 has greater values.

    The lesson asks for O(n) time, visiting each node once.

    Approach: carry the largest value down the path

    A tree node has no link to its parent, so a node can't look back up its own path. The brute force would walk the path again for every node, costing up to O(n * h) for a tree h levels deep. Going down, there is a cheaper way: carry along what you need.

    A node is good exactly when its value is at least the largest value above it. So one number summarises the entire path: the largest value seen so far, here named maxSoFar. A recursive helper countGood(node, maxSoFar) returns the number of good nodes in the tree under node:

    1. An empty tree has no good nodes: return 0.
    2. This node is good if node.value >= maxSoFar.
    3. Compute newMax, the larger of maxSoFar and the node's value. This is the largest value on the path down to the node, node included.
    4. Add the good nodes of the left subtree and of the right subtree, both counted against newMax.

    Both children get the same newMax, because they share the path down to their parent, and nothing in the left branch is on the right branch's path.

    For the first example, the helper sees these nodes and thresholds. Indentation shows depth:

    node 3 maxSoFar=3 good=true
  node 1 maxSoFar=3 good=false
    node 3 maxSoFar=3 good=true
  node 4 maxSoFar=3 good=true
    node 1 maxSoFar=4 good=false
    node 5 maxSoFar=4 good=true

    Four lines say good=true, which is the answer. Notice that the 3 at the bottom is measured against 3, not against its parent's 1: the threshold is the maximum of the whole path.

    Step by step

    1. Start the recursion from goodNodes. It calls countGood(root, root.value) and returns the result. The root's own value is the starting maximum, so the root passes its test.
    2. Write the helper's signature. countGood takes a TreeNode named node and an Int named maxSoFar, and returns an Int.
    3. Handle the empty tree. If node == null, return 0. This also stops the recursion past a leaf.
    4. Declare a counter. var count = 0 will hold this node (if good) plus the good nodes below. It is a var because the next steps change it.
    5. Test this node. If node.value >= maxSoFar, set count to 1. Equal counts as good.
    6. Update the threshold. Store math.max(maxSoFar, node.value) in a val named newMax.
    7. Count the left subtree. Add countGood(node.left, newMax) to count with +=.
    8. Count the right subtree the same way with node.right.
    9. Return count.

    The solution in Scala

    class Solution {
    def countGood(node: TreeNode, maxSoFar: Int): Int = {
        if (node == null) {
            return 0
        }
        var count = 0
        if (node.value >= maxSoFar) {
            count = 1
        }
        val newMax = math.max(maxSoFar, node.value)
        count += countGood(node.left, newMax)
        count += countGood(node.right, newMax)
        return count
    }

    def goodNodes(root: TreeNode): Int = {
        return countGood(root, root.value)
    }
}

    The Scala details worth a closer look:

    • The return type of a recursive method. countGood calls itself, so its result type : Int must be written out.
    • var versus val. count is a var because it is assigned and then increased. newMax is computed once per call and never changes, so it is a val.
    • += on a var. count += countGood(...) means count = count + countGood(...). It works on a var of type Int and would not compile on a val.
    • Passing values down, not up. maxSoFar is a parameter, not a shared variable. Each call has its own copy, so the left subtree's updates can't leak into the right subtree's path.
    • math.max. It is available without an import, through the scala.math package object.
    • The null check. The lesson's TreeNode uses null for a missing child. node == null is safe: it does not throw.
    • return keyword. The solution uses return for early exit, which is legal in a method body. The last expression, count, would be the method's value without it.

    Complexity

    Let n be the number of nodes and h the height of the tree.

    Time: O(n). Each node is visited once, and the work in one call is a comparison, a max and two additions.

    Space: O(h). The only extra memory is the recursion stack, one frame per level: about log n for a balanced tree and up to n for a chain. The lesson limits the depth to 800 levels, and a chain of 800 nodes counts correctly.

    Edge cases and common mistakes

    • A single node. [1] gives 1: the root is always good.
    • Equal values. A tree whose nodes are all 2 ([2, 2, 2, 2, 2]) gives 5, because an equal value is not greater.
    • Negative values. In [-5, -7, -3] the answer is 2: the root and the -3. Starting maxSoFar at 0 would be wrong: on [-3, -5, -2] it gives 0 instead of 2, as every value is below 0, even the root. Starting from the root's own value avoids that.
    • Chains. A decreasing chain 5, 4, 3, 2 has only the root good, and an increasing chain 1, 2, 3, 4 has all four good.
    • Comparing with the parent only. The 3 at the bottom left of the first example sits under a 1, yet it is good. The comparison must be against the maximum of the whole path.
    • Using > instead of >=. Nodes equal to the maximum would be missed, and even the root would fail its own test.
    • Forgetting to update the threshold. If the children are called with maxSoFar instead of newMax, a node is only compared with the values above its parent. Any greater value that sits higher on the path than that is ignored, so nodes that should fail can be counted as good.

    Testing

    • [3, 1, 4, 3, null, 1, 5] gives 4.
    • [3, 3, null, 4, 2] gives 3.
    • [1] gives 1.
    • [-5, -7, -3] gives 2.
    • [5, 4, null, 3, null, 2] (a decreasing chain) gives 1.
    • [1, 2, null, 3, null, 4] (an increasing chain) gives 4.
    • [2, 2, 2, 2, 2] gives 5.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free