Tree - Count Good Nodes in Binary Tree
All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.
Difficulty : Easy
PreOrder dfs()
Problem
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:
1
2
3
4
5
6
7
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.
Example 2:
1
2
3
Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
Example 3:
1
2
3
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Solution
Since we need to consider all the nodes between root and child nodes, we need to run PreOrder traversal for solving this. We also need to track the max_val between any node and its root. The max_val is initially set to root.val.
1
def dfs(root, max_val):
None of the None nodes are Good nodes, hence we can return 0 whenever dfs() function is receiving a None node.
1
2
3
def dfs(root, max_val):
if not root:
return 0
Now, we need to set result to 1 if the current node value is equal to larger than max_val, if not we need to set this to 0.
1
result = 1 if root.val >= max_val else 0
Calculate the max_val using current node so that this value can be passes down.
1
max_val = max(root.val, max_val)
We can now traverse the left and right nodes. We can append the return values from the child nodes to get cumulative total count.
1
2
3
4
result+= dfs(root.left,max_val)
result+= dfs(root.right,max_val)
return result
Visualization
Final Code
Here is the full code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def goodNodes(root: TreeNode):
def dfs(root, max_val):
if not root:
return 0
result = 1 if root.val >= max_val else 0
max_val = max(root.val, max_val)
result += dfs(root.left, max_val)
result += dfs(root.right, max_val)
return result
return dfs(root, root.val)