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.
Examples:
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.
Example 2:
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:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Constraints:
- The number of nodes in the binary tree is in the range
[1, 105]. - Each node’s value is between
-104, 104
Approach
- Use DFS traversal starting from the root.
- Keep track of the maximum value seen so far (
maxSeenSoFar) along the path. - For each node:
- If
node.val >= maxSeenSoFar, it’s a good node → increment count. - Update
maxSeenSoFartoMath.max(curr.val, maxSeenSoFar).
- If
- Recurse for left and right children.
- Return the total count of good nodes.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n) recursion stack space (h=tree height)
Dry Run
Function Call: goodNodes(root) where
root = TreeNode(3)
├── left: TreeNode(1)
│ └── left: TreeNode(3)
└── right: TreeNode(4)
└── right: TreeNode(5)
Step 1:
→ Initialize ans = 0
→ Call traversal(root, -Infinity)
Step 2:
→ curr = 3, maxSeenSoFar = -Infinity
→ 3 >= -Infinity → ans++ → ans = 1
→ currMax = max(-Infinity, 3) = 3
→ Call traversal(curr.left = 1, currMax = 3)
Step 3:
→ curr = 1, maxSeenSoFar = 3
→ 1 >= 3 → false → ans unchanged
→ currMax = max(3, 1) = 3
→ Call traversal(curr.left = 3, currMax = 3)
Step 4:
→ curr = 3, maxSeenSoFar = 3
→ 3 >= 3 → ans++ → ans = 2
→ currMax = max(3, 3) = 3
→ curr.left = null → skip
→ curr.right = null → skip
→ return
Step 5:
→ curr.right = null for node 1 → skip
→ return
Step 6:
→ Back to root, call traversal(curr.right = 4, currMax = 3)
Step 7:
→ curr = 4, maxSeenSoFar = 3
→ 4 >= 3 → ans++ → ans = 3
→ currMax = max(3, 4) = 4
→ curr.left = null → skip
→ Call traversal(curr.right = 5, currMax = 4)
Step 8:
→ curr = 5, maxSeenSoFar = 4
→ 5 >= 4 → ans++ → ans = 4
→ curr.left = null → skip
→ curr.right = null → skip
→ return
Step 9:
→ All calls done → return ans = 4
Final Result: 4
root = TreeNode(3)
├── left: TreeNode(1)
│ └── left: TreeNode(3)
└── right: TreeNode(4)
└── right: TreeNode(5)
Step 1:
→ Initialize ans = 0
→ Call traversal(root, -Infinity)
Step 2:
→ curr = 3, maxSeenSoFar = -Infinity
→ 3 >= -Infinity → ans++ → ans = 1
→ currMax = max(-Infinity, 3) = 3
→ Call traversal(curr.left = 1, currMax = 3)
Step 3:
→ curr = 1, maxSeenSoFar = 3
→ 1 >= 3 → false → ans unchanged
→ currMax = max(3, 1) = 3
→ Call traversal(curr.left = 3, currMax = 3)
Step 4:
→ curr = 3, maxSeenSoFar = 3
→ 3 >= 3 → ans++ → ans = 2
→ currMax = max(3, 3) = 3
→ curr.left = null → skip
→ curr.right = null → skip
→ return
Step 5:
→ curr.right = null for node 1 → skip
→ return
Step 6:
→ Back to root, call traversal(curr.right = 4, currMax = 3)
Step 7:
→ curr = 4, maxSeenSoFar = 3
→ 4 >= 3 → ans++ → ans = 3
→ currMax = max(3, 4) = 4
→ curr.left = null → skip
→ Call traversal(curr.right = 5, currMax = 4)
Step 8:
→ curr = 5, maxSeenSoFar = 4
→ 5 >= 4 → ans++ → ans = 4
→ curr.left = null → skip
→ curr.right = null → skip
→ return
Step 9:
→ All calls done → return ans = 4
Final Result: 4
var goodNodes = function(root) {
let ans = 0;
let traversal = (curr, maxSeenSoFar) =>{
if(curr.val >= maxSeenSoFar){
++ans;
}
let currMax = Math.max(maxSeenSoFar, curr.val);
curr.left && traversal(curr.left, currMax);
curr.right && traversal(curr.right, currMax);
}
traversal(root, -Infinity);
return ans;
};
class Solution:
def goodNodes(self, root):
self.ans = 0
def traversal(curr, max_seen_so_far):
if not curr:
return
if curr.val >= max_seen_so_far:
self.ans += 1
curr_max = max(max_seen_so_far, curr.val)
traversal(curr.left, curr_max)
traversal(curr.right, curr_max)
traversal(root, float('-inf'))
return self.ans
class Solution {
int ans = 0;
public void traversal(TreeNode curr, int maxSeenSoFar) {
if (curr == null) return;
if (curr.val >= maxSeenSoFar) ans++;
int currMax = Math.max(maxSeenSoFar, curr.val);
traversal(curr.left, currMax);
traversal(curr.right, currMax);
}
public int goodNodes(TreeNode root) {
traversal(root, Integer.MIN_VALUE);
return ans;
}
}
class Solution {
public:
int ans = 0;
void traversal(TreeNode* curr, int maxSeenSoFar) {
if (!curr) return;
if (curr->val >= maxSeenSoFar) ans++;
int currMax = max(maxSeenSoFar, curr->val);
traversal(curr->left, currMax);
traversal(curr->right, currMax);
}
int goodNodes(TreeNode* root) {
traversal(root, INT_MIN);
return ans;
}
};
int ans = 0;
void traversal(struct TreeNode* curr, int maxSeenSoFar) {
if (curr == NULL) return;
if (curr->val >= maxSeenSoFar) {
ans++;
}
int currMax = (curr->val > maxSeenSoFar) ? curr->val : maxSeenSoFar;
traversal(curr->left, currMax);
traversal(curr->right, currMax);
}
int goodNodes(struct TreeNode* root) {
ans = 0;
traversal(root, INT_MIN);
return ans;
}
public class Solution {
int ans = 0;
public void Traversal(TreeNode curr, int maxSeenSoFar) {
if (curr == null) return;
if (curr.val >= maxSeenSoFar) ans++;
int currMax = Math.Max(maxSeenSoFar, curr.val);
Traversal(curr.left, currMax);
Traversal(curr.right, currMax);
}
public int GoodNodes(TreeNode root) {
ans = 0;
Traversal(root, int.MinValue);
return ans;
}
}
