Count Good Nodes in Binary Tree

Medium Trees & BST Child + Ancestor Handling Original on LeetCode

Reported atGoldman Sachs

Count Good Nodes in Binary Tree is a medium trees & bst problem solved with the child + ancestor handling pattern. The best approach, optimal (dfs carrying the path maximum), runs in O(n) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan the whole path at every node) up.

Problem

You are given the root of a binary tree. A node X is called good when no node on the path from the root down to X (including the root, excluding X itself) has a value strictly greater than X.val.

Return the number of good nodes in the tree. The root is always good.

Examples

Example 1

Input
root = [5, 3, 8, 6, null, 7, 9]
Output
4
Why
Good nodes: 5 (the root), 6 (path 5-3-6), 8 and 9. The 3 is smaller than 5 and the 7 is smaller than 8.

Example 2

Input
root = [-2, -2, -5]
Output
2
Why
The left child equals the largest value above it, which still counts. -5 is below -2.

Example 3

Input
root = [4]
Output
1
Why
The root has nothing above it, so it is always good.

Constraints

  • The number of nodes is in the range [1, 10^5].
  • -10^4 <= Node.val <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan the whole path at every node)O(n · h)O(h)
Optimal (DFS carrying the path maximum)O(n)O(h)

1Brute force (scan the whole path at every node)

TimeO(n · h)Each node scans up to h ancestors, where h is the tree height.
SpaceO(h)The path list and the recursion stack both hold at most h entries.

Traverse the tree while keeping the list of values on the current root-to-node path. At each node, scan that list to see if any ancestor is larger.

  1. DFS with a list path of ancestor values.
  2. At a node, it is good if no value in path exceeds node.val.
  3. Add node.val to the path, recurse into both children, then remove it.
class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, new ArrayList<>());
    }

    private int dfs(TreeNode node, List<Integer> path) {
        if (node == null) return 0;
        boolean good = true;
        for (int v : path)
            if (v > node.val) { good = false; break; }
        path.add(node.val);
        int count = (good ? 1 : 0) + dfs(node.left, path) + dfs(node.right, path);
        path.remove(path.size() - 1);
        return count;
    }
}

2Optimal (DFS carrying the path maximum)

TimeO(n)Every node is visited once with constant work.
SpaceO(h)Recursion depth equals the tree height.

The scan in the brute force only ever needs the maximum of the path, and that maximum can be updated in O(1) on the way down. Pass it as an argument: a node is good when its value is at least the maximum, and its children receive max(maximum, node.val).

  1. dfs(node, maxSoFar): if node is null return 0.
  2. good = node.val >= maxSoFar ? 1 : 0; newMax = max(maxSoFar, node.val).
  3. Return good + dfs(left, newMax) + dfs(right, newMax). Start with dfs(root, root.val).
class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, root.val);
    }

    private int dfs(TreeNode node, int maxSoFar) {
        if (node == null) return 0;
        int good = node.val >= maxSoFar ? 1 : 0;
        int next = Math.max(maxSoFar, node.val);
        return good + dfs(node.left, next) + dfs(node.right, next);
    }
}

Edge cases to test

  • A single node (answer 1)
  • Values equal to the path maximum count as good
  • A strictly decreasing chain (only the root is good)
  • A strictly increasing chain (every node is good)
  • Negative values

Hints

Hint 1

Whether a node is good only depends on the largest value on the path from the root to it.

Hint 2

Pass that largest value down as a parameter while you traverse.

FAQ

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

Optimal (DFS carrying the path maximum) runs in O(n) time and O(h) extra space. Every node is visited once with constant work.

Which pattern does Count Good Nodes in Binary Tree use?

It is a trees & bst problem that uses the child + ancestor handling pattern. Other problems with the same pattern: Amount of Time for Binary Tree to Be Infected, Burning Tree, All Nodes Distance K in Binary Tree.

Is there a brute force solution for Count Good Nodes in Binary Tree?

Yes. Brute force (scan the whole path at every node) takes O(n · h) time and O(h) space. Traverse the tree while keeping the list of values on the current root-to-node path.

Which edge cases should I test for Count Good Nodes in Binary Tree?

A single node (answer 1); Values equal to the path maximum count as good; A strictly decreasing chain (only the root is good); A strictly increasing chain (every node is good); Negative values.