Count Good Nodes in Binary Tree Leetcode Solution

Problem Statement

In this problem a binary tree is given with its 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.

 

We have to return the number of good nodes in the given binary tree.

Example

3

/

1 4

/ /

3 1 5

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

And Node 3 -> (3,1,3) is the maximum value in the path.

3

/

3

/

4 2

3

Explanation:

 

Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Approach

To find whether a node is good or not we must traverse path from root to the that node and check if its value is not smaller than maximum in this path.

To find the number of good nodes we have to check like this for each node of the given binary tree. But here observe one thing,

 

if we find the answer for a particular node by traversing its path from root, we can go to its child node also from there itself because we have already traversed almost path of child node also and we also have maximum value traversed till yet. We just have to update the maximum with current node value to transfer to its both children node.

So this looks like a DFS or recursion where to go to a particular node we traverse the path from root to that node. Thus in this problem recursion will be very helpful.

 

www.tutorialcup.com/leetcode-solutions/count-good-nodes-i...

Done