Count Good Nodes in Binary Tree

LeetCode 1544 | Difficulty: Medium

Medium

Problem 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.

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, 10^5]`.

- Each node's value is between `[-10^4, 10^4]`.

Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

Tree BFS (Level-Order)

Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.

When to use

Level-order traversal, level-based aggregation, right/left side view.

---

Solutions

Solution 1: C# (Best: 172 ms)

Metric	Value
Runtime	172 ms
Memory	45.1 MB
Date	2021-09-19

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int GoodNodes(TreeNode root)
{
    if(root==null) return 0;
        int count = 0;
    int max = Int32.MinValue;
    GoodNodes(root, max, ref count);
    return count;    
}

public void GoodNodes(TreeNode root, int max, ref int count)
{
    if(root==null) return;
    if(root.val >= max)
    {
        count++;
        max = root.val;
    }
    GoodNodes(root.left, max, ref count);
    GoodNodes(root.right, max, ref count);  
}
}

📜 2 more C# submission(s)

Submission (2021-09-19) — 305 ms, 45.3 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int GoodNodes(TreeNode root)
{
    int count = 0;
    int max = Int32.MinValue;
    GoodNodes(root, max, ref count);
    return count;    
}

public void GoodNodes(TreeNode root, int max, ref int count)
{
    if(root==null) return;
    if(root.val >= max)
    {
        count++;
    }
    max = Math.Max(max, root.val);
    GoodNodes(root.left, max, ref count);
    GoodNodes(root.right, max, ref count);  
}
}

Submission (2021-09-19) — 403 ms, 46.5 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int GoodNodes(TreeNode root)
{
    int count = 0;
    int max = Int32.MinValue;
    GoodNodes(root, max, ref count);
    return count;    
}

public void GoodNodes(TreeNode root, int max, ref int count)
{
    if(root==null) return;
    if(root.val >= max)
    {
        count++;
        max = root.val;
    }
    GoodNodes(root.left, max, ref count);
    GoodNodes(root.right, max, ref count);  
}
}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use DFS (Depth First Search) to traverse the tree, and constantly keep track of the current path maximum.