Count Good Nodes in a Binary Tree
Description
Hello, young coder! 🌟 We're going to have some fun with binary trees today. But wait, what's a binary tree? 🌳 Well, imagine a family tree, but each parent node can only have two children. In our case, each node contains a number, and it also has a left and a right child, which could be None if there's no child there.
Now, our task is to count something we call "good nodes" in this binary tree. What's a good node? A node is considered "good" if the value it holds is the largest value encountered on the path from the root to this node.
A "good node" means that if you're traveling from the root to that node, that node has a value greater than or equal to all the previous nodes' values on that path.
Example Execution:
# Assuming TreeNode is defined as:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Example input:
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.left = TreeNode(3)
root.right.left = TreeNode(1)
root.right.right = TreeNode(5)
count_good_nodes(root) # Output: 4
Let's count some good nodes in a binary tree! 🌲✨
Inputs
Arg 1:
{"val":3,"left":{"val":1,"left":{"val":3,"left":null,"right":null},"right":null},"right":{"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}Expected Output
4Actual Output