Problem of The Day: Count Good Nodes in Binary Tree

Problem Statement

leetcode problem link

My Solution [Accepted]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int res = 0;
    public int GoodNodes(TreeNode root) {
        if (root is null)
            return 0;
        Helper(root, root.val);
        return res;
    }

    public void Helper(TreeNode root, int currMax) {
        if (root is null) {
            return;
        }
        if (root.val >= currMax) {
            res++;
        }
        Helper(root.left, Math.Max(currMax, root.val));
        Helper(root.right, Math.Max(currMax, root.val));
    }
}

Editorial

Approach 1: Depth First Search, Recursion

class Solution:
    def goodNodes(self, root: TreeNode) -> int:

        def dfs(node, max_so_far):
            nonlocal num_good_nodes
            if max_so_far <= node.val:
                num_good_nodes += 1
            if node.right:
                dfs(node.right, max(node.val, max_so_far))
            if node.left:
                dfs(node.left, max(node.val, max_so_far))

        num_good_nodes = 0
        dfs(root, float("-inf"))
        return num_good_nodes

Approach 2: Depth First Search, Iterative

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        stack = [(root, float("-inf"))]
        num_good_nodes = 0
        while stack:
            node, max_so_far = stack.pop()
            if max_so_far <= node.val:
                num_good_nodes += 1
            if node.left:
                stack.append((node.left, max(node.val, max_so_far)))
            if node.right:
                stack.append((node.right, max(node.val, max_so_far)))

        return num_good_nodes

Approach 3: Breadth First Search

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        num_good_nodes = 0

        # Use collections.deque for efficient popping
        queue = deque([(root, float("-inf"))])
        while queue:
            node, max_so_far = queue.popleft()
            if max_so_far <= node.val:
                num_good_nodes += 1
            if node.right:
                queue.append((node.right, max(node.val, max_so_far)))
            if node.left:
                queue.append((node.left, max(node.val, max_so_far)))

        return num_good_nodes