Leetcode 1448: Count Good Nodes in Binary Tree

In this Leetcode problem, we try to count the good nodes in a binary tree, defined as node for which all the node from root to that node are not greater than the node value.

Problem statement

Solution

This problem is adapted to a recursive type solution of the depth-first-search type, because:

1. The result for a particular node depends only on the parents chain
2. We only need to the know max value in the parents chain to find if the node is good. This max value is easy to pass around recursively

We use the following recursion formula:

goodNodes(node) = goodNodes(node.right) 
    + goodNodes(node.left)
    + (isNodeGood(node) ? 1 : 0)

The stopping condition is that goodNodes(null) = 0 .

To find isNodeGood we need to pass the max value in the parent chain recursively.

The time complexity is O(n) with n the number of nodes in the tree, since we visit each node once. The space complexity is the O(h) with h the height of the tree because of the recursion calls.

Here is the full code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}…