Maximum 69 Number

Description

You are given a binary tree rooted at root. A node X in the tree is called a good node if, on the path from the root of the tree down to X, there is no node whose value is strictly greater than the value of X.

In simpler terms, as you walk from the root toward any node, that node is "good" if its value is greater than or equal to every ancestor value you passed through on the way.

Return the total number of good nodes in the binary tree.

Note that the root node is always considered a good node because there are no ancestors above it.

Examples

Example 1

Input: root = [3, 1, 4, 3, null, 1, 5]

Output: 4

Explanation: The tree looks like this:

Node 3 (root): Good — it is the root, no ancestors to compare.
Node 1 (left child of root): Not good — its ancestor 3 is greater than 1.
Node 4 (right child of root): Good — path is [3, 4], and 4 ≥ 3.
Node 3 (left child of node 1): Good — path is [3, 1, 3], and 3 ≥ max(3, 1) = 3.
Node 1 (left child of node 4): Not good — path is [3, 4, 1], and 4 > 1.
Node 5 (right child of node 4): Good — path is [3, 4, 5], and 5 ≥ max(3, 4) = 4.

Total good nodes = 4.

Example 2

Input: root = [3, 3, null, 4, 2]

Output: 3

Explanation: The tree looks like this:

Node 3 (root): Good — always a good node.
Node 3 (left child): Good — path [3, 3], and 3 ≥ 3.
Node 4: Good — path [3, 3, 4], and 4 ≥ max(3, 3) = 3.
Node 2: Not good — path [3, 3, 2], and 3 > 2.

Total good nodes = 3.

Example 3

Input: root = [1]

Output: 1

Explanation: The tree has only one node (the root). The root is always good because there are no ancestors above it. Total good nodes = 1.

Constraints

1 ≤ number of nodes in the binary tree ≤ 10^5
-10^4 ≤ Node.val ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward way to determine whether a node is good is to explicitly collect the entire path from the root down to that node, then check if the node's value is greater than or equal to every value along that path.

Imagine you are walking through a forest of numbered signposts along branching trails. At each signpost, you turn around and look at every sign you passed to get here. If none of them shows a number bigger than the current sign, you mark this signpost as "good."

We can do this programmatically by traversing the tree. For every node, we maintain a list of all ancestor values from the root down to the current node. Then we simply scan this list to see if any ancestor has a value larger than the current node's value. If not, the node is good.

This approach works correctly but carries extra overhead because for every single node, we look through the entire path of ancestors accumulated so far.

Step-by-Step Explanation

Let's trace through with root = [3, 1, 4, 3, null, 1, 5]:

Step 1: Start at root (value 3). Path = [3]. Check: is 3 ≥ max of path? max([3]) = 3, and 3 ≥ 3. Yes → good node. Count = 1.

Step 2: Move to left child (value 1). Path = [3, 1]. Check: is 1 ≥ max([3, 1])? max = 3, and 1 < 3. No → not good. Count = 1.

Step 3: Move to left child of node 1 (value 3). Path = [3, 1, 3]. Check: is 3 ≥ max([3, 1, 3])? max = 3, and 3 ≥ 3. Yes → good node. Count = 2.

Step 4: Backtrack to node 1. Node 1 has no right child. Backtrack to root.

Step 5: Move to right child (value 4). Path = [3, 4]. Check: is 4 ≥ max([3, 4])? max = 4, and 4 ≥ 4. Yes → good node. Count = 3.

Step 6: Move to left child of node 4 (value 1). Path = [3, 4, 1]. Check: is 1 ≥ max([3, 4, 1])? max = 4, and 1 < 4. No → not good. Count = 3.

Step 7: Backtrack. Move to right child of node 4 (value 5). Path = [3, 4, 5]. Check: is 5 ≥ max([3, 4, 5])? max = 5, and 5 ≥ 5. Yes → good node. Count = 4.

Result: Total good nodes = 4.

Brute Force — Checking Every Ancestor Path — We traverse each node, collect the full path from root, and scan the path to see if any ancestor value exceeds the current node's value.

Algorithm

Start a DFS traversal from the root, maintaining a list (path) of ancestor values.
At each node:
- Compute the maximum value in the current path list.
- If the node's value ≥ that maximum, increment the good node counter.
Add the current node's value to the path list.
Recursively visit the left child and right child, passing the updated path.
After returning from both children, remove the current node's value from the path (backtrack).
Return the total good node count.

Code

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

class Solution {
public:
    int goodNodes(TreeNode* root) {
        vector<int> path;
        int count = 0;
        dfs(root, path, count);
        return count;
    }
    
    void dfs(TreeNode* node, vector<int>& path, int& count) {
        if (!node) return;
        
        // Scan entire path to find maximum
        int maxInPath = INT_MIN;
        for (int val : path) {
            maxInPath = max(maxInPath, val);
        }
        
        if (node->val >= maxInPath) {
            count++;
        }
        
        path.push_back(node->val);
        dfs(node->left, path, count);
        dfs(node->right, path, count);
        path.pop_back();
    }
};

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:
        self.count = 0
        self.dfs(root, [])
        return self.count
    
    def dfs(self, node, path):
        if not node:
            return
        
        # Scan entire path to find maximum
        max_in_path = max(path) if path else float('-inf')
        
        if node.val >= max_in_path:
            self.count += 1
        
        path.append(node.val)
        self.dfs(node.left, path)
        self.dfs(node.right, path)
        path.pop()

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

class Solution {
    private int count = 0;
    
    public int goodNodes(TreeNode root) {
        List<Integer> path = new ArrayList<>();
        dfs(root, path);
        return count;
    }
    
    private void dfs(TreeNode node, List<Integer> path) {
        if (node == null) return;
        
        // Scan entire path to find maximum
        int maxInPath = Integer.MIN_VALUE;
        for (int val : path) {
            maxInPath = Math.max(maxInPath, val);
        }
        
        if (node.val >= maxInPath) {
            count++;
        }
        
        path.add(node.val);
        dfs(node.left, path);
        dfs(node.right, path);
        path.remove(path.size() - 1);
    }
}

Complexity Analysis

Time Complexity: O(n × h)

We visit every node once via DFS — that is O(n). At each node, we scan the entire ancestor path to find the maximum, which takes O(h) time where h is the height of the tree. In the worst case (skewed tree), h = n, leading to O(n²). For balanced trees, h = log n, giving O(n log n).

Space Complexity: O(h)

The path list stores at most h values (the depth of the current node), and the recursion stack also goes h levels deep. So total space is O(h), which is O(n) in the worst case for a skewed tree.

Why This Approach Is Not Efficient

The brute force scans the entire ancestor path at every node just to find the maximum value. For a skewed tree with 10^5 nodes, this means up to 10^5 scans of length up to 10^5, resulting in roughly 10^10 operations — far too slow.

The core inefficiency is that we recompute the maximum from scratch at every node, even though the path only changes by one element as we move from parent to child. If we simply carry the running maximum as a single value down the recursion, each node can determine its good-or-not status in O(1) instead of O(h).

This insight — replacing a repeated O(h) scan with a single O(1) variable — is what makes the optimal approach possible.

Optimal Approach - DFS with Running Maximum

Intuition

Instead of storing the full path and scanning it at each node, we only need to track one piece of information: the maximum value seen so far along the current path from root to this node.

Why does this work? A node is good if its value is ≥ every ancestor value. That is equivalent to saying its value is ≥ the single largest ancestor. So we only need the maximum, not the whole list.

Think of it like climbing a mountain with checkpoints. You do not need to remember the altitude at every checkpoint you passed — you just remember the highest altitude you have reached so far. At the current checkpoint, if your altitude is at least as high as that record, you mark it as a "peak" checkpoint.

As we do a DFS traversal, we pass maxSoFar to each recursive call. When visiting a child, we update maxSoFar to include the current node's value. Each node does a simple O(1) comparison instead of scanning a list.

Step-by-Step Explanation

Let's trace through with root = [3, 1, 4, 3, null, 1, 5]:

Step 1: Call dfs(root=3, maxSoFar=-∞). Node 3 ≥ -∞ → good. Update maxSoFar = max(-∞, 3) = 3. Count = 1.

Step 2: Call dfs(left=1, maxSoFar=3). Node 1 < 3 → not good. Update maxSoFar = max(3, 1) = 3 (unchanged). Count = 1.

Step 3: Call dfs(left=3, maxSoFar=3). Node 3 ≥ 3 → good. Update maxSoFar = max(3, 3) = 3. Count = 2.

Step 4: Node 3 has no children. Backtrack to node 1. Node 1 has no right child. Backtrack to root.

Step 5: Call dfs(right=4, maxSoFar=3). Node 4 ≥ 3 → good. Update maxSoFar = max(3, 4) = 4. Count = 3.

Step 6: Call dfs(left=1, maxSoFar=4). Node 1 < 4 → not good. Update maxSoFar = max(4, 1) = 4. Count = 3.

Step 7: Node 1 has no children. Backtrack.

Step 8: Call dfs(right=5, maxSoFar=4). Node 5 ≥ 4 → good. Count = 4.

Step 9: Node 5 has no children. All traversal complete. Return 4.

DFS with Running Maximum — O(1) Per Node Check — Watch how carrying a single maxSoFar value down the recursion lets each node decide if it is good in constant time, without rescanning ancestors.

Algorithm

Define a helper function dfs(node, maxSoFar) that returns the count of good nodes in the subtree rooted at node.
Base case: if node is null, return 0.
If node.val >= maxSoFar, this node is good — set count = 1; otherwise count = 0.
Update maxSoFar = max(maxSoFar, node.val).
Recursively call dfs(node.left, maxSoFar) and dfs(node.right, maxSoFar).
Return count + leftResult + rightResult.
Invoke the helper with dfs(root, -∞) (or root.val since root is always good).

Code

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

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, INT_MIN);
    }
    
    int dfs(TreeNode* node, int maxSoFar) {
        if (!node) return 0;
        
        int count = (node->val >= maxSoFar) ? 1 : 0;
        maxSoFar = max(maxSoFar, node->val);
        
        count += dfs(node->left, maxSoFar);
        count += dfs(node->right, maxSoFar);
        
        return count;
    }
};

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:
        def dfs(node, max_so_far):
            if not node:
                return 0
            
            count = 1 if node.val >= max_so_far else 0
            max_so_far = max(max_so_far, node.val)
            
            count += dfs(node.left, max_so_far)
            count += dfs(node.right, max_so_far)
            
            return count
        
        return dfs(root, float('-inf'))

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

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }
    
    private int dfs(TreeNode node, int maxSoFar) {
        if (node == null) return 0;
        
        int count = (node.val >= maxSoFar) ? 1 : 0;
        maxSoFar = Math.max(maxSoFar, node.val);
        
        count += dfs(node.left, maxSoFar);
        count += dfs(node.right, maxSoFar);
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every node exactly once. At each node, we do a single O(1) comparison (node value vs. maxSoFar) and a single O(1) max operation. Therefore, the total work across all n nodes is O(n).

Space Complexity: O(h)

The space is dominated by the recursion call stack, which goes as deep as the height h of the tree. In the worst case (completely skewed tree), h = n, so space is O(n). For a balanced tree, h = log n, giving O(log n) space.

Compared to the brute force, we eliminated the O(h) per-node scan, reducing total time from O(n × h) to O(n), while using the same O(h) space.