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.
Solution:
Time Complexity : O(n)
Space Complexity: O(height of the tree)
// DFS solution
var goodNodes = function(root, max = root.val) {
let output = 0
// Only add to output if we meet the condition
if(root.val >= max) output++
// Increase the max if we encounter a val greater than max
max = Math.max(Math.max(root.val, max))
// Traverse the tree to compare more nodes
if(root.left) output += goodNodes(root.left, max)
if(root.right) output += goodNodes(root.right, max)
return output
};
Top comments (0)