Count Good Nodes in Binary Tree

NeetCode: Count Good Nodes in Binary Tree · LeetCode: 1448. Count Good Nodes in Binary Tree · Difficulty: Medium

A node X is good if no node on the path from the root to X has a value greater than X. Count the good nodes. The root is always good.

Example

Text

Input:  [3, 1, 4, 3, null, 1, 5]    Output: 4    (3, 4, 3, 5)

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: check the whole path at each node

Carry the list of ancestors down the recursion, and for every node test it against all of them. path.remove(path.size() - 1) removes by index. Calling remove with an Integer value would remove the first matching value instead.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private int count(TreeNode node, List<Integer> path) {
        if (node == null) {
            return 0;
        }
        int good = 1;
        for (int ancestor : path) {
            if (ancestor > node.val) {
                good = 0;
                break;
            }
        }
        path.add(node.val);
        int total = good + count(node.left, path) + count(node.right, path);
        path.remove(path.size() - 1); // remove by index, not by value
        return total;
    }

    public int goodNodes(TreeNode root) {
        return count(root, new ArrayList<>());
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.goodNodes(tree(3, 1, 4, 3, null, 1, 5)));
        System.out.println(s.goodNodes(tree(3, 3, null, 4, 2)));
    }
}

Output

4
3

Time: O(n * h), up to O(n²) for a chain. Space: O(h).

Optimal: carry the maximum so far

A node is good exactly when its value is at least the maximum on its path. Pass that single number down instead of the whole path, updating it at each node. The starting value Integer.MIN_VALUE makes the root good for any int value, because every int is at least Integer.MIN_VALUE.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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

    public int goodNodes(TreeNode root) {
        return count(root, Integer.MIN_VALUE);
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.goodNodes(tree(3, 1, 4, 3, null, 1, 5)));
        System.out.println(s.goodNodes(tree(3, 3, null, 4, 2)));
    }
}

Output

4
3

Time: O(n). Space: O(h).

Interview points

A node is good when its value is at least the maximum value on the path from the root.
Carrying one maximum replaces the per-node scan of the whole path.
The root is always good, which the starting value Integer.MIN_VALUE guarantees.

Summary

Brute force: O(n * h) time. Optimal: O(n) time.
Both use O(h) space for the recursion.
Equal values count as good (>=, not >).