Count Good Nodes In Binary Tree

Problem

Given a binary tree, a node is called "good" if the path from the root down to that node contains no value greater than the node's own value. Return the number of good nodes in the tree.

Examples

Constraints

• 1 <= number of nodes <= 10^5

How to approach it: the Trees pattern

A tree is a hierarchical structure where each node has at most a fixed number of children (two, for binary trees). Almost every tree problem reduces to a traversal — decide what order you visit nodes in, and what you do at each one.

Look for this pattern when

• The problem is naturally recursive: "the answer for this tree depends on the answer for its subtrees."
• You need level-by-level information (BFS) versus depth-first structural information (DFS).

Read the full Trees guide →

Video walkthroughs

• Python walkthrough on YouTube ↗
• C++ walkthrough by Code with Alisha ↗

Original problem on LeetCode ↗

More Trees problems

• Invert Binary Tree Easy
• Maximum Depth of Binary Tree Easy
• Same Tree Easy
• Subtree of Another Tree Easy
• Lowest Common Ancestor of a Binary Search Tree Medium
• Binary Tree Level Order Traversal Medium
• Validate Binary Search Tree Medium
• Kth Smallest Element In a Bst Medium
• Construct Binary Tree From Preorder And Inorder Traversal Medium
• Binary Tree Maximum Path Sum Hard
• Serialize And Deserialize Binary Tree Hard
• Diameter of Binary Tree Easy
• Balanced Binary Tree Easy
• Binary Tree Right Side View Medium