1448. Count Good Nodes in Binary Tree - Solution

The problem

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

Approach overview

Problem Overview: You are given the root of a binary tree. A node is considered good if no node on the path from the root to that node has a value greater than it. The task is to count how many such nodes exist in the tree.

Approach 1: Recursive Depth First Search (DFS) (Time: O(n), Space: O(h))

Traverse the tree using DFS while carrying the maximum value seen on the path from the root to the current node. When visiting a node, compare its value with the running maximum. If node.val >= max_so_far, the node is good and you increment the count. Update the running maximum with max(max_so_far, node.val) before continuing the recursion to the left and right children. Every node is visited exactly once, giving O(n) time complexity. The recursion stack uses O(h) space where h is the tree height (worst case O(n), balanced tree O(log n)). This approach naturally fits problems involving path-based constraints in a binary tree and is the most common interview solution using depth-first search.

Approach 2: Iterative Breadth First Search (BFS) (Time: O(n), Space: O(n))

The same idea can be implemented iteratively with a queue using breadth-first search. Store pairs in the queue: the current node and the maximum value seen along the path to that node. When dequeuing, check if the node value is greater than or equal to the stored maximum. If it is, count it as a good node and update the path maximum for its children. Push each child into the queue with the updated maximum value. Since each node is processed once, the traversal runs in O(n) time. The queue may hold up to an entire level of the tree, giving O(n) auxiliary space in the worst case.

Recommended for interviews: Recursive DFS is typically expected. It directly models the path constraint by passing the current maximum down the recursion. Interviewers often want to see that you recognize the pattern of carrying state along a root-to-node path. The BFS version demonstrates the same idea iteratively and is useful if recursion depth could become an issue.

Approach 1: Recursive Depth First Search (DFS)

This approach uses a recursive depth-first search strategy, where we traverse the tree starting from the root. As we traverse, we maintain the maximum value encountered on the path from the root to the current node. A node is considered 'good' if its value is greater than or equal to the maximum value on this path. We use a recursive helper function that updates the count of good nodes accordingly.

Python

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

class Solution:
    def dfs(self, node, maxVal):
        if not node:
            return 0
        good = 1 if node.val >= maxVal else 0
        maxVal = max(maxVal, node.val)
        return good + self.dfs(node.left, maxVal) + self.dfs(node.right, maxVal)

    def goodNodes(self, root):
        return self.dfs(root, root.val)

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private int dfs(TreeNode node, int maxVal) {
        if (node == null) return 0;
        int count = 0;
        if (node.val >= maxVal) count = 1;
        maxVal = Math.max(maxVal, node.val);
        count += dfs(node.left, maxVal);
        count += dfs(node.right, maxVal);
        return count;
    }

    public int goodNodes(TreeNode root) {
        return dfs(root, root.val);
    }
}

C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int dfs(TreeNode* node, int maxVal) {
        if (!node) return 0;
        int good = 0;
        if (node->val >= maxVal) good = 1;
        maxVal = max(maxVal, node->val);
        return good + dfs(node->left, maxVal) + dfs(node->right, maxVal);
    }

    int goodNodes(TreeNode* root) {
        return dfs(root, root->val);
    }
};

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

const goodNodes = function(root) {
    const dfs = (node, maxVal) => {
        if (!node) return 0;
        let good = 0;
        if (node.val >= maxVal) good = 1;
        maxVal = Math.max(maxVal, node.val);
        good += dfs(node.left, maxVal);
        good += dfs(node.right, maxVal);
        return good;
    };
    return dfs(root, root.val);
};

#include <stdlib.h>
#include <stdio.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int dfs(struct TreeNode* node, int maxVal) {
    if (!node) return 0;
    int total = 0;
    if (node->val >= maxVal) total = 1;
    maxVal = (node->val > maxVal) ? node->val : maxVal;
    total += dfs(node->left, maxVal);
    total += dfs(node->right, maxVal);
    return total;
}

int goodNodes(struct TreeNode* root) {
    if (!root) return 0;
    return dfs(root, root->val);
}

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 {
    private int Dfs(TreeNode node, int maxVal) {
        if (node == null) return 0;
        int good = (node.val >= maxVal) ? 1 : 0;
        maxVal = Math.Max(maxVal, node.val);
        good += Dfs(node.left, maxVal);
        good += Dfs(node.right, maxVal);
        return good;
    }

    public int GoodNodes(TreeNode root) {
        return Dfs(root, root.val);
    }
}

This Python solution utilizes a helper function dfs within the class Solution. It employs recursion to traverse the tree and count the good nodes as per the conditions provided.

Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(h), where h is the height of the tree.

Try this approach in the editor

Approach 2: Iterative Breadth First Search (BFS)

This approach utilizes an iterative method with a queue to perform a breadth-first search (BFS) on the binary tree. As we traverse, we maintain the maximum value encountered from the root to the current node using a pair of node and max value stored in the queue. At each step, we check if the current node is a good node and update our count.

Python

from collections import deque

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

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = deque([(root, root.val)])
        goodCount = 0
        while queue:
            node, maxVal = queue.popleft()
            if node.val >= maxVal:
                goodCount += 1
            if node.left:
                queue.append((node.left, max(maxVal, node.val)))
            if node.right:
                queue.append((node.right, max(maxVal, node.val)))
        return goodCount

Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int goodNodes(TreeNode root) {
        if (root == null) return 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, root.val));
        int goodCount = 0;
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            TreeNode node = p.getKey();
            int maxVal = p.getValue();
            if (node.val >= maxVal) goodCount++;
            if (node.left != null) queue.add(new Pair<>(node.left, Math.max(node.val, maxVal)));
            if (node.right != null) queue.add(new Pair<>(node.right, Math.max(node.val, maxVal)));
        }
        return goodCount;
    }
}

C++

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int goodNodes(TreeNode* root) {
        if (!root) return 0;
        queue<pair<TreeNode*, int>> q;
        q.push({root, root->val});
        int goodNodesCount = 0;
        while (!q.empty()) {
            auto [node, maxVal] = q.front(); q.pop();
            if (node->val >= maxVal) goodNodesCount++;
            if (node->left) q.push({node->left, max(maxVal, node->val)});
            if (node->right) q.push({node->right, max(maxVal, node->val)});
        }
        return goodNodesCount;
    }
};

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

const goodNodes = function(root) {
    if (!root) return 0;
    const queue = [{ node: root, maxVal: root.val }];
    let goodCount = 0;
    while (queue.length) {
        const { node, maxVal } = queue.shift();
        if (node.val >= maxVal) goodCount++;
        if (node.left) queue.push({ node: node.left, maxVal: Math.max(maxVal, node.val) });
        if (node.right) queue.push({ node: node.right, maxVal: Math.max(maxVal, node.val) });
    }
    return goodCount;
};

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct QueueNode {
    struct TreeNode* node;
    int maxVal;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

void enqueue(struct Queue* q, struct TreeNode* node, int maxVal) {
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->node = node;
    newNode->maxVal = maxVal;
    newNode->next = NULL;
    if (!q->rear) q->front = q->rear = newNode;
    else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

struct TreeNode* dequeue(struct Queue* q, int* maxVal) {
    if (!q->front) return NULL;
    struct QueueNode* temp = q->front;
    *maxVal = temp->maxVal;
    struct TreeNode* node = temp->node;
    q->front = q->front->next;
    if (!q->front) q->rear = NULL;
    free(temp);
    return node;
}

int goodNodes(struct TreeNode* root) {
    if (!root) return 0;
    struct Queue q = {NULL, NULL};
    enqueue(&q, root, root->val);
    int goodCount = 0;
    while (q.front) {
        int maxVal;
        struct TreeNode* node = dequeue(&q, &maxVal);
        if (node->val >= maxVal) goodCount++;
        if (node->left) enqueue(&q, node->left, node->val >= maxVal ? node->val : maxVal);
        if (node->right) enqueue(&q, node->right, node->val >= maxVal ? node->val : maxVal);
    }
    return goodCount;
}

using System;
using System.Collections.Generic;

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;
        Queue<(TreeNode, int)> queue = new Queue<(TreeNode, int)>();
        queue.Enqueue((root, root.val));
        int goodCount = 0;
        while (queue.Count > 0) {
            (TreeNode node, int maxVal) = queue.Dequeue();
            if (node.val >= maxVal) goodCount++;
            if (node.left != null) queue.Enqueue((node.left, Math.Max(maxVal, node.val)));
            if (node.right != null) queue.Enqueue((node.right, Math.Max(maxVal, node.val)));
        }
        return goodCount;
    }
}

The Python solution makes use of a deque from the collections module to implement the BFS. Each dequeued element is a tuple of the current node and the maximum value seen from the root to that node, allowing proper evaluation and update of the good nodes count.

Complexity

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function goodNodes(root: TreeNode | null): number {
    let ans = 0;
    const dfs = (root: TreeNode | null, mx: number) => {
        if (!root) {
            return;
        }
        if (mx <= root.val) {
            ++ans;
            mx = root.val;
        }
        dfs(root.left, mx);
        dfs(root.right, mx);
    };
    dfs(root, -1e6);
    return ans;
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func goodNodes(root *TreeNode) (ans int) {
	var dfs func(*TreeNode, int)
	dfs = func(root *TreeNode, mx int) {
		if root == nil {
			return
		}
		if mx <= root.Val {
			ans++
			mx = root.Val
		}
		dfs(root.Left, mx)
		dfs(root.Right, mx)
	}
	dfs(root, -10001)
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Depth First Search (DFS)	Time Complexity: O(n), where n is the number of nodes in the binary tree. Space Complexity: O(h), where h is the height of the tree.
Iterative Breadth First Search (BFS)	Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(w), where w is the maximum width of the tree.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Depth First Search (DFS)	O(n)	O(h)	Preferred interview solution. Clean recursion and natural for path-based tree problems.
Iterative Breadth First Search (BFS)	O(n)	O(n)	Useful when avoiding recursion or when processing nodes level by level.

Frequently asked questions

Is Count Good Nodes in Binary Tree easy or hard?

The problem is rated Medium because it requires recognizing a path-based condition during tree traversal. Once you realize you must carry the maximum value along the root-to-node path, the implementation using DFS or BFS becomes straightforward.

Count Good Nodes in Binary Tree Python/Java solution

In both Python and Java, the typical solution uses DFS recursion with a parameter representing the maximum value seen so far. Each recursive call checks the current node against this maximum and updates it before exploring children. The logic is identical across languages and runs in O(n) time.

How to solve Count Good Nodes in Binary Tree in O(n)?

Traverse the tree while maintaining the maximum value seen on the path from the root to the current node. During DFS or BFS, compare the current node value with this maximum. If it is greater than or equal, increment the good node count and update the maximum before continuing traversal. Since each node is processed once, the algorithm runs in O(n) time.

What is the best approach for Count Good Nodes in Binary Tree?

Recursive Depth First Search (DFS) is the most common approach. Track the maximum value seen along the path from the root to the current node and compare it with the current node value. If the node value is greater than or equal to the maximum so far, it is counted as a good node. The traversal visits each node once, giving O(n) time complexity.

Is Count Good Nodes in Binary Tree asked at Google/Amazon/Meta?

Tree traversal and path constraint problems like this frequently appear in interviews at large tech companies including Amazon, Google, and Meta. Variations that involve tracking values along root-to-node paths are common in technical screening rounds.

What data structure is used in Count Good Nodes in Binary Tree?

The core data structure is a binary tree. The algorithm typically uses recursion with the call stack for DFS or a queue for BFS traversal while storing the current node and the maximum value seen along its path.

What is the time complexity of Count Good Nodes in Binary Tree?

The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during traversal. Space complexity is O(h) for recursive DFS due to the recursion stack, where h is the tree height, or O(n) when using an iterative BFS queue.

Count Good Nodes in Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth First Search (DFS)

Approach 2: Iterative Breadth First Search (BFS)

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Good Nodes in Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth First Search (DFS)

Approach 2: Iterative Breadth First Search (BFS)

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems