August leetcoding challenge - Count Good Nodes in Binary Tree

Problem Statement

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example:1

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Approach

The problem statement says that , we have to find out the number of good nodes in a given binary tree where a node is called good node if in the path from root to the node , there is no greater value than the current node.

So the idea here is , we can say a node to be a good node by comparing the current node value with the value that is maximum from root to current node. If current node value is greater than the maximum we can consider the current node as good node.

Now the problem boils down to keeping track of the maximum value from root to any node "x".

We can solve this problem iteratively using level order traversal of a binary tree.

Pseudo code

We will be using level order traversal of a binary tree to solve this problem. Level order traversing of a tree is nothing but traversing the tree level by level.

Initialize a count variable and queue to keep track of the nodes of the tree.
Append root node and root node value as a tuple to the queue . In this tuple first element represents the node and second element represents the maximum value seen from root to this node(keeping track of maximum value for comparision)
Follow below steps until queue is empty:

1. Pop the item (node,maximum) from the queue - where each item in queue represents the the node and the maximum value have till now from root to node
2. check if the node value is greater than the maximum . If yes increment the count by 1
3. If node has the left child - append left child to the queue along with maximum value seen till now from root node to the current node.left
4. If node has the right child - append the right child to the queue along with the maximum value seen till now from root node to the current node.right.
5. Return count once queue is empty - queue empty represents that we have visited all the nodes of the binary tree.

code

from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        count = 0
        queue = deque()
        queue.append((root,root.val))
        while len(queue)>0:
            popped,value = queue.popleft()
            if popped.val >= value:
                count+=1
            if popped.left:  
             queue.append((popped.left,max(popped.left.val,value)))
            if popped.right:   
           queue.append((popped.right,max(popped.right.val,value)))
        return count

Open for any discussions!