Count good nodes in a binary tree, according to LeatCode this is Microsoft’s most asked interview question of 2021 so far.
I think it’s a pretty good problem to understand. A lot of basic Tree fundamental knowledge can be gained from this problem.
So we’re given the root of a binary tree that is going to always be non-empty. We want to count the number of good nodes in the tree.
There is a good node if, from the root node all the way down to the node, there are no nodes in that path that have a greater value than this particular node.
Let’s see the problem statement:
The tree can be solved linearly in O(n) time, with n being the number of nodes and memory complexity being O(long), in other words, the tree’s height which theoretically can be greater than log n.
This can be accomplished with a simple tree traversal, specifically by using pre-order traversals.
When we recursively run DFS on the given tree. We will recursively process each node, as well as its left and right subtrees tree.
Example:
Technically, the root node is always a good node, adding the root to the good nodes, we will move to the left and right subtrees and find out how many good nodes are there in the left subtree and how many good nodes are there in the right subtree.
Lets see the code:
Method 1: DFS using recursion
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def dfs(node, max_val):
if node is None:
return 0
count = 1 if node.val >= max_val else 0
max_val = max(max_val, node.val)
count += dfs(node.left, max_val)
count += dfs(node.right, max_val)
return count
return dfs(root, root.val)Method 2: DFS using iterative
class Solution:
def goodNodes(self, root: TreeNode) -> int:
array = []
count = 0
if root:
array.append((root, root.val))
while array:
(current, current_max) = array.pop()
if current.val >= current_max: count += 1
if current.right:
array.append((current.right, max(current_max, current.right.val)))
if current.left:
array.append((current.left, max(current_max, current.left.val)))
return count