Count Good Nodes in Binary Tree

▶

Steps

setup

Initialize stack with root node

We start by initializing the stack with the root node (value 3) and its value as the initial maxVal. The count of good nodes is zero.

💡 This sets up the traversal starting point and the baseline maxVal for comparisons.

Line:

stack = [(root, root.val)]
count = 0

💡 The root node is always a good node because it has no ancestors.

traverse

Pop root node from stack and check if good

Pop the root node (3) and its maxVal (3) from the stack. Since node.val (3) >= maxVal (3), increment count to 1.

💡 Checking if the current node is good by comparing its value to maxVal is the core logic.

Line:

node, max_val = stack.pop()
if node.val >= max_val:
    count += 1

💡 Good nodes are those that are at least as large as any node on the path from root.

traverse

Update maxVal after visiting root

Update maxVal to max(3, 3) = 3 after visiting the root node.

💡 maxVal must track the highest value seen on the path to correctly identify good nodes.

Line:

max_val = max(max_val, node.val)

💡 maxVal carries forward the maximum value seen so far on the path.

expand

Push right child (4) with maxVal 3 onto stack

Push the right child node (4) of root onto the stack with maxVal 3.

💡 We push right child first so that left child is processed next (stack LIFO).

Line:

if node.right:
    stack.append((node.right, max_val))

💡 Children are pushed with the current maxVal to maintain correct comparisons downstream.

expand

Push left child (1) with maxVal 3 onto stack

Push the left child node (1) of root onto the stack with maxVal 3. Left child will be processed next.

💡 Pushing left child last ensures it is popped first, simulating preorder traversal.

Line:

if node.left:
    stack.append((node.left, max_val))

💡 Stack order controls traversal order: left child next, then right child.

traverse

Pop left child (1) and check if good

Pop node 1 with maxVal 3. Since 1 < 3, count remains unchanged.

💡 Nodes smaller than maxVal on path are not good nodes.

Line:

node, max_val = stack.pop()
if node.val >= max_val:
    count += 1

💡 Good nodes must be >= maxVal on path; this node fails that test.

traverse

Update maxVal after visiting node 1

Update maxVal to max(3, 1) = 3 after visiting node 1.

💡 maxVal remains unchanged because node 1 is smaller.

Line:

max_val = max(max_val, node.val)

💡 maxVal only increases or stays the same as we traverse.

expand

Push right child of node 1 (none) - skip

Node 1 has no right child, so nothing is pushed onto the stack.

💡 No right child means no expansion on this side.

Line:

if node.right:
    stack.append((node.right, max_val))

💡 Leaves or missing children do not add to stack.

expand

Push left child (3) of node 1 with maxVal 3

Push left child node (3) of node 1 onto the stack with maxVal 3.

💡 This child may be a good node if its value >= maxVal.

Line:

if node.left:
    stack.append((node.left, max_val))

💡 Children are pushed with updated maxVal to continue traversal.

traverse

Pop left child (3) of node 1 and check if good

Pop node 3 (child of node 1) with maxVal 3. Since 3 >= 3, increment count to 2.

💡 This node is good because it matches or exceeds maxVal on path.

Line:

node, max_val = stack.pop()
if node.val >= max_val:
    count += 1

💡 Good nodes can appear deeper in the tree if they meet the maxVal condition.

traverse

Update maxVal after visiting node 3 (child of 1)

Update maxVal to max(3, 3) = 3 after visiting this node.

💡 maxVal remains the same because node value equals maxVal.

Line:

max_val = max(max_val, node.val)

💡 maxVal carries forward unchanged when node value equals maxVal.

traverse

Pop right child (4) of root and check if good

Pop node 4 with maxVal 3. Since 4 >= 3, increment count to 3.

💡 Node 4 is good because it exceeds maxVal on path.

Line:

node, max_val = stack.pop()
if node.val >= max_val:
    count += 1

💡 Good nodes can increase maxVal for their descendants.

traverse

Update maxVal after visiting node 4

Update maxVal to max(3, 4) = 4 after visiting node 4.

💡 maxVal increases to 4, affecting children nodes.

Line:

max_val = max(max_val, node.val)

💡 maxVal updates dynamically as we find larger node values.

expand

Push right child (5) of node 4 with maxVal 4

Push right child node (5) of node 4 onto the stack with maxVal 4.

💡 Right child pushed first to process left child next.

Line:

if node.right:
    stack.append((node.right, max_val))

💡 Children inherit updated maxVal from parent node.

expand

Push left child (1) of node 4 with maxVal 4

Push left child node (1) of node 4 onto the stack with maxVal 4.

💡 Left child pushed last to be processed next.

Line:

if node.left:
    stack.append((node.left, max_val))

💡 Stack order ensures left subtree is processed before right.

traverse

Pop left child (1) of node 4 and check if good

Pop node 1 with maxVal 4. Since 1 < 4, count remains 3.

💡 Node 1 is not good because it is smaller than maxVal.

Line:

node, max_val = stack.pop()
if node.val >= max_val:
    count += 1

💡 Not all descendants are good nodes; value must meet maxVal condition.

traverse

Update maxVal after visiting node 1 (child of 4)

Update maxVal to max(4, 1) = 4 after visiting this node.

💡 maxVal remains 4 since node value is smaller.

Line:

max_val = max(max_val, node.val)

💡 maxVal only increases or stays the same as traversal continues.

traverse

Pop right child (5) of node 4 and check if good

Pop node 5 with maxVal 4. Since 5 >= 4, increment count to 4.

💡 Node 5 is good because it exceeds maxVal on path.

Line:

node, max_val = stack.pop()
if node.val >= max_val:
    count += 1

💡 Good nodes can appear deep and increase maxVal for their descendants.

traverse

Update maxVal after visiting node 5

Update maxVal to max(4, 5) = 5 after visiting node 5.

💡 maxVal increases to 5, but node 5 has no children.

Line:

max_val = max(max_val, node.val)

💡 maxVal reflects the highest value on the path at each step.

reconstruct

Traversal complete, return count

Stack is empty, traversal is complete. Return the count of good nodes, which is 4.

💡 The final count represents the total good nodes found.

Line:

return count

💡 The algorithm correctly counted all good nodes in the tree.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_good_nodes(root):
    if not root:
        return 0
    count = 0  # STEP 1
    stack = [(root, root.val)]  # STEP 1
    while stack:  # STEP 2
        node, max_val = stack.pop()  # STEP 2
        if node.val >= max_val:  # STEP 2
            count += 1  # STEP 2
        max_val = max(max_val, node.val)  # STEP 3
        if node.right:  # STEP 4
            stack.append((node.right, max_val))  # STEP 4
        if node.left:  # STEP 5
            stack.append((node.left, max_val))  # STEP 5
    return count  # STEP 20

if __name__ == '__main__':
    root = TreeNode(3)  # Setup
    root.left = TreeNode(1, TreeNode(3))
    root.right = TreeNode(4, TreeNode(1), TreeNode(5))
    print(count_good_nodes(root))  # Output: 4

📊

Count Good Nodes in Binary Tree - Watch the Algorithm Execute, Step by Step

Watching each stack operation and comparison helps you understand how the algorithm tracks the maximum value on the path and counts nodes accordingly.

314315

DFS Stack

1 (entered)max_val=3

Current node: 1

314315

Current node: 1

314315

314315

DFS Stack

3 (entered)max_val=3

314315

DFS Stack

2 (entered)max_val=33 (entered)max_val=3

Current node: 2

314315

DFS Stack

3 (entered)max_val=3

Current node: 2

314315

DFS Stack

3 (entered)max_val=3

Current node: 2

314315

DFS Stack

3 (entered)max_val=3

314315

DFS Stack

4 (entered)max_val=33 (entered)max_val=3

Current node: 4

314315

DFS Stack

3 (entered)max_val=3

Current node: 4

314315

DFS Stack

3 (entered)max_val=3

Current node: 3

314315

Current node: 3

314315

Current node: 3

314315

DFS Stack

6 (entered)max_val=4

Current node: 3

314315

DFS Stack

5 (entered)max_val=46 (entered)max_val=4

Current node: 5

314315

DFS Stack

6 (entered)max_val=4

Current node: 5

314315

DFS Stack

6 (entered)max_val=4

Current node: 6

314315

Current node: 6

314315

314315

Return: 4

Key Takeaways

✓ The algorithm uses a stack to simulate preorder DFS, tracking maxVal on the path to identify good nodes.

This insight is hard to see from code alone because the stack and maxVal propagation are implicit in recursion or iterative code.

✓ Stack order (push right child before left) ensures left subtree is processed first, matching preorder traversal.

Visualizing the stack clarifies traversal order, which is often confusing when reading code.

✓ Good nodes are counted only when node.val >= maxVal, showing how maxVal acts as a threshold updated dynamically.

Seeing each comparison and count increment step-by-step reveals the core decision logic.

Practice

1. Given a binary tree, you need to return the values of its nodes level by level starting from the bottom-most level up to the root. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Perform a standard level order traversal (BFS) and then reverse the collected levels at the end.

B. Use a depth-first search (DFS) with level tracking to collect nodes per level, then reverse the levels after traversal.

C. Apply a greedy approach by always visiting the right child before the left child to get bottom-up order.

D. Use dynamic programming to store subtrees' bottom-up levels and merge them.

Solution

1. Step 1: Understand problem requirements

   The problem requires collecting nodes level by level from bottom to top, which is not a simple BFS traversal order.

2. Step 2: Identify approach that naturally collects levels bottom-up

   Performing a standard BFS collects nodes level by level from top to bottom. Reversing the collected levels at the end yields the bottom-up order efficiently and straightforwardly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS with reversal is optimal and simple [OK]

Hint: Bottom-up levels are easiest with BFS and reversal [OK]

Common Mistakes:

• Assuming DFS alone gives bottom-up order without reversal
• Using greedy traversal order incorrectly

2. You need to collect nodes of a binary tree grouped by their depth level, from top to bottom, left to right. Which algorithmic approach guarantees an optimal solution that visits each node exactly once and groups nodes by their level?

easy

A. Use a Depth-First Search (DFS) without tracking levels, then sort nodes by depth after traversal.

B. Use a recursive approach that collects nodes in preorder traversal order.

C. Use Breadth-First Search (BFS) with a queue to process nodes level by level.

D. Use a greedy approach that picks the leftmost node at each level before moving to the next.

Solution

1. Step 1: Understand the problem requirement

   The problem requires grouping nodes by their depth level, visiting nodes level by level from top to bottom and left to right.

2. Step 2: Evaluate algorithm suitability

   BFS with a queue naturally processes nodes level by level, ensuring each node is visited once and grouped correctly. DFS without level tracking or greedy approaches do not guarantee correct grouping or order.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS processes nodes in level order by design [OK]

Hint: BFS naturally processes nodes level by level [OK]

Common Mistakes:

• Thinking DFS without level tracking groups nodes by level
• Assuming greedy leftmost picks produce level order
• Sorting after DFS is inefficient

3. You are given a binary tree where each node may have zero, one, or two children. Your task is to connect each node's next pointer to its next right node on the same level. If there is no next right node, the next pointer should be set to NULL. Which approach guarantees an optimal solution with O(n) time and O(h) space, where h is the tree height?

easy

A. Use a dynamic programming approach to store connections and build them bottom-up.

B. Perform a level order traversal using a queue to connect nodes level by level.

C. Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.

D. Apply a greedy approach that connects nodes as soon as they are discovered during DFS.

Solution

1. Step 1: Understand the problem constraints

   The problem requires connecting next pointers in any binary tree, not necessarily perfect or complete, with O(n) time and O(h) space.

2. Step 2: Evaluate approaches

   Using a queue (Perform a level order traversal using a queue to connect nodes level by level.) uses O(n) space, violating the space constraint. DP (Use a dynamic programming approach to store connections and build them bottom-up.) is not applicable here. Greedy DFS (Apply a greedy approach that connects nodes as soon as they are discovered during DFS.) fails to guarantee correct connections across siblings at the same level. The recursive top-down approach (Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.) uses existing next pointers to traverse levels efficiently with O(h) recursion stack space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Top-down recursion with next pointers -> O(n) time, O(h) space [OK]

Hint: Top-down recursion uses next pointers to avoid extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Trying DP bottom-up which doesn't fit this problem
• Using DFS greedily without next pointers

4. You are given a perfect binary tree where each node has two children. The task is to connect each node's next pointer to its immediate right neighbor on the same level, or NULL if there is none. Which approach guarantees an optimal solution with O(1) extra space and O(n) time complexity?

easy

A. Use the already established next pointers to traverse each level and connect children without extra space.

B. Perform a level order traversal using a queue to connect nodes at each level.

C. Apply a dynamic programming approach to store and connect nodes level-wise.

D. Use a depth-first search recursion to connect nodes from top to bottom.

Solution

1. Step 1: Understand the problem constraints

   The tree is perfect, so every node has two children, and all leaves are at the same level.

2. Step 2: Identify the approach that uses constant extra space

   Using next pointers already set on the current level to connect the next level avoids extra data structures like queues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses existing pointers to traverse levels [OK]

Hint: Use next pointers to traverse levels without extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Confusing DFS recursion with constant space
• Using DP which is unrelated

5. Suppose the vertical order traversal problem is extended so that nodes can appear multiple times if they have the same column and row but different parents (e.g., in a graph-like structure with shared nodes). Which modification to the BFS with column tracking approach correctly handles this scenario?

hard

A. Modify BFS to track (node, column, row) and store nodes in a list keyed by (column, row), then sort by parent ID

B. Use DFS with sorting by column, row, and parent to order nodes

C. Use BFS with column tracking but ignore row and parent, just append nodes as visited

D. Use BFS with column tracking and a visited set to avoid revisiting nodes

Solution

1. Step 1: Understand problem extension

   Nodes can appear multiple times if they share column and row but differ by parent, so row and parent info must be tracked.

2. Step 2: Evaluate modifications

   Tracking (node, column, row) and sorting by parent ID ensures correct ordering. Ignoring row or parent loses correctness. Visited set prevents duplicates but may skip valid repeats.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracking row and parent allows correct ordering of duplicates [OK]

Hint: Track row and parent to distinguish duplicates in BFS [OK]

Common Mistakes:

• Ignoring row or parent info leads to incorrect grouping
• Using visited set that skips valid repeated nodes