Posts Count Good Nodes in Binary Tree
Post
Cancel

Count Good Nodes in Binary Tree

PROBLEM DESCRIPTION

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.

Leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    
    public int goodNodes(TreeNode root) {
        //root.val will be the current maximum for root 
        return goodNodesHelper(root, root.val);
    }

    public int goodNodesHelper(TreeNode root, int max){
        
        //if root is null, it's not a "good node"
        if(root == null) return 0;

        //if the current value is more than the max till now, we have got a good node
        //+1 and check in LST and RST
        //also update the max to current node since that is the new max
        if(root.val >= max){
            return 1 + goodNodesHelper(root.left, root.val) + goodNodesHelper(root.right, root.val);
        //else, the current node is not a good node since it is lower than the max
        //so, keep checking with the same max in LST and RST
        }else{
            return goodNodesHelper(root.left, max) + goodNodesHelper(root.right, max);
        }

    }

}
This post is licensed under CC BY 4.0 by the author.