LeetCode: Counting “Good Nodes” in a Binary Tree

Problem Statement

A node X in a binary tree is “good” if no nodes in the path from the root to X have a greater value than X. We need to count all of the good nodes in the binary tree.

Intuition

My first thought when hearing that problem was (shamefully): let’s write a recursive method that checks if a path array is “good” (last element is max), increments a good count if so, adds the current value to the path array, and passes that array down in another recursive call until we reach a leaf (no children).

My second thought: maybe passing an increasingly long list as an argument to recursive function calls is not the proper approach. Especially since this would involve both recursion (traversing down the tree) and iteration (path list checking at each node). Yuck.

Approach

What we ultimately want to check is that the value of the current node in the traversal down the tree is greater than or equal to all of the node values above it. To do this, instead of passing down a list (an ArrayList of integers), we just need to pass down a currentMax, and update it if we encounter a node with a value that’s higher.

If the current node value is greater than or equal to the current max passed in as an argument (before any updates), it’s a “good” node, so we can add 1 to our good node count. From there, we’re just interested in the good node counts from the left and right subtrees, so we update the max and recursively call the same function on the left and right children, and we return the total sum of the good nodes back down the stack.

And, of course, with any recursion, we have our base case, which is a node that’s null. Rather than checking if node.left is null or node.right is null before invoking recursively, we can simply check if the current node is null at the beginning of the method and return 0 immediately if so because a null node is not “good” since it has no value.

Complexity

• Time complexity: O(n). We’re performing a depth first search traversal of a binary tree and each node is visited exactly once; for each node, a constant amount of work is being done (checking that node.val >= currentMax and updating currentMax)
• Space complexity: Since the function uses recursive depth first search, the space complexity is determined by the depth of our recursion stack. We make a recursive call for each level of the binary tree, so O(h) is the worst case complexity, where h is the height of the tree. Of course, the tree can be balanced, where h = log n, or skewed, where h = n.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution { 
    public int goodNodes(TreeNode root) {
        return goodNodes(root, root.val);
    }

    public int goodNodes(TreeNode node, int currentMax) { 
            if (node == null) {
                return 0;
            }
            int goodNode = node.val >= currentMax ? 1 : 0; 
            currentMax = node.val > currentMax ? node.val : currentMax;
            return goodNode + goodNodes(node.left, currentMax) + goodNodes(node.right, currentMax);
        }
    }