Problem editorial

Count Good Nodes in Binary Tree

MediumTree Traversal Patterns (DFS & BFS)Binary TreeDepth-First SearchTree

Editorial

Core insight

Count Good Nodes in Binary Tree · Tree Traversal Patterns (DFS & BFS)

Core Insight for Count Good Nodes in Binary Tree

The brute force method repeatedly examines the same root-to-node prefixes. Preorder traversal removes that repeated work by carrying the necessary path information forward as the traversal descends.

For every visited node, maintain:

text

maximum = largest value among the node's ancestors and itself so far

Before updating this value with the current node, compare:

text

node.value >= maximum

If this condition is true, the node is good. After processing the node, compute the state for both children:

text

nextMaximum = max(maximum, node.value)

The key invariant is:

Whenever a node is removed from the traversal stack, its associated maximum is the largest value on the path from the root to its parent, together with the value already established for the current path state.

Because each child receives the maximum from its exact root-to-child path, the good-node condition is evaluated against precisely the required values.

Visual Description

The traversal starts with one stack entry for the root and its initial path maximum. When a node is processed, its stack state is removed, the node is evaluated, and up to two child states are added. The left and right branches therefore form separate DFS paths, each carrying its own updated maximum. The recursion tree is represented by stack frames of the form (node, pathMaximum); no path state from one branch is reused incorrectly by the other.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 1448: Count Good Nodes in Binary Tree Solution & Explanation

Problem Overview

TL;DR: Traverse the tree in preorder DFS while carrying the maximum value seen on the current root-to-node path, and count a node whenever its value is at least that maximum.

In LeetCode 1448: Count Good Nodes in Binary Tree, a node is good if no earlier node on the path from the root has a greater value. The root-to-node path includes the node itself, so the root is always good when the tree is non-empty.

The goal is to return the number of good nodes. This is a popular interview question because it tests binary tree traversal, path-dependent state, and recursive preorder reasoning. The optimal solution for interviews runs in linear time.

Brute Force Approach for Count Good Nodes in Binary Tree

A direct approach is to evaluate each node independently:

Start at the current node.
Walk from the root to that node.
Track the maximum value on that path.
Count the node if its value is equal to that maximum.

This requires finding or reconstructing the root-to-node path for every node.

Naive Pseudocode

text

function countGoodNodes(root):
    if root is null:
        return 0

    count = 0

    for each node in the tree:
        path = findPath(root, node)
        maximum = maximum value in path

        if node.value >= maximum:
            count += 1

    return count

If the tree is highly unbalanced, the path to a node can contain up to N nodes, where N is the total number of nodes. Repeating this work for all nodes leads to:

Time complexity: O(N²) in the worst case
Space complexity: O(N) for path storage or search state

With up to 10^5 nodes, an O(N²) traversal can require roughly 10^10 operations in a degenerate tree. That is not practical and can result in Time Limit Exceeded.

Algorithm Strategy: Tree Traversal Patterns (DFS & BFS)

Use preorder depth-first traversal with an explicit stack.

Each stack entry stores:

The binary tree node to process
The maximum value associated with its root-to-node path

For each entry:

Check whether the node value is at least the stored path maximum.
Increment the answer if it is good.
Update the maximum using the current node value.
Push the children with that updated maximum.

The stack preserves the DFS traversal state explicitly. Each branch receives the path boundary that applies to that branch, so the maximum from one branch cannot affect another.

Execution Flow

If root is null, return 0.
Initialize the count to 0.
Push (root, root.val) onto the stack.
While the stack is not empty:
1. Remove the most recently pushed (node, maximum) entry.
2. Check whether node.val >= maximum.
3. Increment the count if the condition is true.
4. Compute currentMaximum = max(maximum, node.val).
5. Push the right child with currentMaximum, if it exists.
6. Push the left child with currentMaximum, if it exists.
Return the final count.

Because the right child is pushed before the left child, the left child is processed first, matching preorder DFS behavior: current node, left subtree, right subtree.

Proof of Correctness

We prove that the algorithm returns the number of good nodes.

Invariant

For every stack entry (node, maximum), maximum is the largest value on the path from the root to node, including the value of node when the entry is initialized or updated according to the implementation's state convention.

At the root, the stored maximum is root.val, which is the maximum on the root's path.

Assume the invariant holds when a node is processed. The algorithm checks whether:

text

node.val >= maximum

Since maximum represents the largest value on the root-to-node path, this condition is true exactly when the node's value is greater than or equal to every value on that path. Therefore, the algorithm counts the node if and only if it is good.

The algorithm then computes:

text

currentMaximum = max(maximum, node.val)

This is the largest value on the path extended to each child. Consequently, every child receives the correct maximum for its own root-to-child path, preserving the invariant.

Every node is pushed and processed exactly once. Since each node is counted exactly when it satisfies the definition of a good node, the final count is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

All of these problems use depth-first traversal to process nodes in a controlled order while carrying or updating path-specific state. The state differs by problem: mirrored nodes for symmetry, structural rewiring for flattening, path contents for binary tree paths, and path strings for the smallest leaf-to-root string. LeetCode 1448: Count Good Nodes in Binary Tree carries the maximum value along the current preorder path.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 1448

cpp

1class Solution {
2public:
3    int goodNodes(TreeNode* root) {
4        if (root == nullptr) {
5            return 0;
6        }
7
8        int count = 0;
9        std::vector<std::pair<TreeNode*, int>> stack;
10        stack.push_back({root, root->val});
11
12        while (!stack.empty()) {
13            TreeNode* node = stack.back().first;
14            int pathMaximum = stack.back().second;
15            stack.pop_back();
16
17            if (node->val >= pathMaximum) {
18                ++count;
19            }
20
21            int nextMaximum = std::max(pathMaximum, node->val);
22            if (node->right != nullptr) {
23                stack.push_back({node->right, nextMaximum});
24            }
25            if (node->left != nullptr) {
26                stack.push_back({node->left, nextMaximum});
27            }
28        }
29
30        return count;
31    }
32};

Java Solution for LeetCode 1448

java

1class Solution {
2    public int goodNodes(TreeNode root) {
3        if (root == null) {
4            return 0;
5        }
6
7        int count = 0;
8        java.util.ArrayDeque<Frame> stack = new java.util.ArrayDeque<>();
9        stack.push(new Frame(root, root.val));
10
11        while (!stack.isEmpty()) {
12            Frame frame = stack.pop();
13            TreeNode node = frame.node;
14            int maximum = frame.maximum;
15            int currentMaximum = Math.max(maximum, node.val);
16
17            if (node.val >= maximum) {
18                count++;
19            }
20
21            if (node.left != null) {
22                stack.push(new Frame(node.left, currentMaximum));
23            }
24            if (node.right != null) {
25                stack.push(new Frame(node.right, currentMaximum));
26            }
27        }
28
29        return count;
30    }
31
32    private static class Frame {
33        TreeNode node;
34        int maximum;
35
36        Frame(TreeNode node, int maximum) {
37            this.node = node;
38            this.maximum = maximum;
39        }
40    }
41}

Python Solution for LeetCode 1448

python

1class Solution:
2    def goodNodes(self, root: Optional[TreeNode]) -> int:
3        if root is None:
4            return 0
5
6        count = 0
7        stack = [(root, root.val)]
8
9        while stack:
10            node, maximum = stack.pop()
11            current_maximum = max(maximum, node.val)
12
13            if node.val >= maximum:
14                count += 1
15
16            if node.left is not None:
17                stack.append((node.left, current_maximum))
18            if node.right is not None:
19                stack.append((node.right, current_maximum))
20
21        return count

AI Coach Insight

For Count Good Nodes in Binary Tree, focus on explaining why the structure works, not just naming Tree Traversal Patterns (DFS & BFS).

Complexity Analysis

Let N be the number of nodes.

Time complexity: O(N)
Each node is pushed, removed, and processed once.
Space complexity: O(N) in the worst case
The explicit DFS stack can contain O(N) entries for a highly unbalanced tree. For a balanced tree, the stack is typically O(log N).

Related Patterns

Pattern: Tree Traversal Patterns (DFS & BFS)
Subpattern: Recursive Preorder Traversal

This problem fits the recursive preorder traversal pattern because each node must be processed before its children, and the state passed to each child depends on the path from the root.

The verified implementations use an explicit stack rather than the language call stack. This is an iterative simulation of the same preorder DFS pattern and avoids recursion-depth problems when the tree contains up to 10^5 nodes.

Common Mistakes & FAQ

Why does the naive solution TLE?

The naive solution searches the root-to-node path separately for every node. In a skewed tree, many of these paths overlap and contain nearly the entire tree. Repeating this work produces O(N²) time, which is too slow for 10^5 nodes. The preorder traversal pattern avoids recomputation by carrying the current maximum forward once.

Why should the maximum be passed separately for each child?

Each child belongs to a different root-to-node path. The state for a child must be derived from its own ancestors, not from nodes in another branch. Sharing or globally mutating one maximum without restoring the correct branch state can cause values from the left subtree to affect the right subtree, producing incorrect counts.

Why is the comparison `node.val >= maximum` rather than `node.val > maximum`?

A node is good when its value is greater than or equal to every value before it on the path. Equal values are allowed. Using > incorrectly excludes nodes whose value ties the path maximum.

Why must the root be initialized with `root.val`?

The root is always good in a non-empty tree. Initializing the root's path maximum with its own value makes the comparison true immediately and establishes the correct state for both child paths.

Why is the updated maximum passed to the children?

A child's path includes its parent. If the current node is larger than the previous maximum, that value must become the boundary for both child paths. Passing the old maximum would allow descendants to be incorrectly counted as good even when the current node is larger.

Why use an explicit stack when the pattern is recursive preorder traversal?

A recursive implementation follows the same logical pattern, but a tree with 10^5 nodes can exceed the language's call-stack limit. The explicit stack stores the same traversal frames manually and provides the same preorder state transitions without relying on deep recursion.

Practise Count Good Nodes in Binary Tree and the problems around it

Count Good Nodes in Binary Tree is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Preorder Traversal subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Count Good Nodes in Binary Tree · Tree Traversal Patterns (DFS & BFS)

Core Insight for Count Good Nodes in Binary Tree

The brute force method repeatedly examines the same root-to-node prefixes. Preorder traversal removes that repeated work by carrying the necessary path information forward as the traversal descends.

For every visited node, maintain:

text

maximum = largest value among the node's ancestors and itself so far

Before updating this value with the current node, compare:

text

node.value >= maximum

If this condition is true, the node is good. After processing the node, compute the state for both children:

text

nextMaximum = max(maximum, node.value)

The key invariant is:

Whenever a node is removed from the traversal stack, its associated maximum is the largest value on the path from the root to its parent, together with the value already established for the current path state.

Because each child receives the maximum from its exact root-to-child path, the good-node condition is evaluated against precisely the required values.

Visual Description

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 1448: Count Good Nodes in Binary Tree Solution & Explanation

Problem Overview

TL;DR: Traverse the tree in preorder DFS while carrying the maximum value seen on the current root-to-node path, and count a node whenever its value is at least that maximum.

Brute Force Approach for Count Good Nodes in Binary Tree

A direct approach is to evaluate each node independently:

Start at the current node.
Walk from the root to that node.
Track the maximum value on that path.
Count the node if its value is equal to that maximum.

This requires finding or reconstructing the root-to-node path for every node.

Naive Pseudocode

text

function countGoodNodes(root):
    if root is null:
        return 0

    count = 0

    for each node in the tree:
        path = findPath(root, node)
        maximum = maximum value in path

        if node.value >= maximum:
            count += 1

    return count

If the tree is highly unbalanced, the path to a node can contain up to N nodes, where N is the total number of nodes. Repeating this work for all nodes leads to:

Time complexity: O(N²) in the worst case
Space complexity: O(N) for path storage or search state

With up to 10^5 nodes, an O(N²) traversal can require roughly 10^10 operations in a degenerate tree. That is not practical and can result in Time Limit Exceeded.

Algorithm Strategy: Tree Traversal Patterns (DFS & BFS)

Use preorder depth-first traversal with an explicit stack.

Each stack entry stores:

The binary tree node to process
The maximum value associated with its root-to-node path

For each entry:

Check whether the node value is at least the stored path maximum.
Increment the answer if it is good.
Update the maximum using the current node value.
Push the children with that updated maximum.

The stack preserves the DFS traversal state explicitly. Each branch receives the path boundary that applies to that branch, so the maximum from one branch cannot affect another.

Execution Flow

If root is null, return 0.
Initialize the count to 0.
Push (root, root.val) onto the stack.
While the stack is not empty:
1. Remove the most recently pushed (node, maximum) entry.
2. Check whether node.val >= maximum.
3. Increment the count if the condition is true.
4. Compute currentMaximum = max(maximum, node.val).
5. Push the right child with currentMaximum, if it exists.
6. Push the left child with currentMaximum, if it exists.
Return the final count.

Because the right child is pushed before the left child, the left child is processed first, matching preorder DFS behavior: current node, left subtree, right subtree.

Proof of Correctness

We prove that the algorithm returns the number of good nodes.

Invariant

At the root, the stored maximum is root.val, which is the maximum on the root's path.

Assume the invariant holds when a node is processed. The algorithm checks whether:

text

node.val >= maximum

The algorithm then computes:

text

currentMaximum = max(maximum, node.val)

This is the largest value on the path extended to each child. Consequently, every child receives the correct maximum for its own root-to-child path, preserving the invariant.

Every node is pushed and processed exactly once. Since each node is counted exactly when it satisfies the definition of a good node, the final count is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 1448

cpp

1class Solution {
2public:
3    int goodNodes(TreeNode* root) {
4        if (root == nullptr) {
5            return 0;
6        }
7
8        int count = 0;
9        std::vector<std::pair<TreeNode*, int>> stack;
10        stack.push_back({root, root->val});
11
12        while (!stack.empty()) {
13            TreeNode* node = stack.back().first;
14            int pathMaximum = stack.back().second;
15            stack.pop_back();
16
17            if (node->val >= pathMaximum) {
18                ++count;
19            }
20
21            int nextMaximum = std::max(pathMaximum, node->val);
22            if (node->right != nullptr) {
23                stack.push_back({node->right, nextMaximum});
24            }
25            if (node->left != nullptr) {
26                stack.push_back({node->left, nextMaximum});
27            }
28        }
29
30        return count;
31    }
32};

Java Solution for LeetCode 1448

java

1class Solution {
2    public int goodNodes(TreeNode root) {
3        if (root == null) {
4            return 0;
5        }
6
7        int count = 0;
8        java.util.ArrayDeque<Frame> stack = new java.util.ArrayDeque<>();
9        stack.push(new Frame(root, root.val));
10
11        while (!stack.isEmpty()) {
12            Frame frame = stack.pop();
13            TreeNode node = frame.node;
14            int maximum = frame.maximum;
15            int currentMaximum = Math.max(maximum, node.val);
16
17            if (node.val >= maximum) {
18                count++;
19            }
20
21            if (node.left != null) {
22                stack.push(new Frame(node.left, currentMaximum));
23            }
24            if (node.right != null) {
25                stack.push(new Frame(node.right, currentMaximum));
26            }
27        }
28
29        return count;
30    }
31
32    private static class Frame {
33        TreeNode node;
34        int maximum;
35
36        Frame(TreeNode node, int maximum) {
37            this.node = node;
38            this.maximum = maximum;
39        }
40    }
41}

Python Solution for LeetCode 1448

python

1class Solution:
2    def goodNodes(self, root: Optional[TreeNode]) -> int:
3        if root is None:
4            return 0
5
6        count = 0
7        stack = [(root, root.val)]
8
9        while stack:
10            node, maximum = stack.pop()
11            current_maximum = max(maximum, node.val)
12
13            if node.val >= maximum:
14                count += 1
15
16            if node.left is not None:
17                stack.append((node.left, current_maximum))
18            if node.right is not None:
19                stack.append((node.right, current_maximum))
20
21        return count

Core Insight for Count Good Nodes in Binary Tree

Visual Description

LeetCode 1448: Count Good Nodes in Binary Tree Solution & Explanation

Problem Overview

Brute Force Approach for Count Good Nodes in Binary Tree

Naive Pseudocode

Algorithm Strategy: Tree Traversal Patterns (DFS & BFS)

Execution Flow

Proof of Correctness

Invariant

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 1448

Java Solution for LeetCode 1448

Python Solution for LeetCode 1448

Practise Count Good Nodes in Binary Tree and the problems around it

Related problems

Core Insight for Count Good Nodes in Binary Tree

Visual Description

LeetCode 1448: Count Good Nodes in Binary Tree Solution & Explanation

Problem Overview

Brute Force Approach for Count Good Nodes in Binary Tree

Naive Pseudocode

Algorithm Strategy: Tree Traversal Patterns (DFS & BFS)

Execution Flow

Proof of Correctness

Invariant

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 1448

Java Solution for LeetCode 1448

Python Solution for LeetCode 1448

Practise Count Good Nodes in Binary Tree and the problems around it

Related problems