Count Good Nodes In Binary Tree

The problem

root is the top node of a binary tree, or null when the tree is empty. Each node has a number val, which can be negative, and up to two children, left and right; a missing child is null. The path to a node is the list of nodes you pass going down from the root to it, with both ends included. A node is good if no node on its path has a larger value than it. Equal values do not count against it. The root is always good, because its path holds only itself. Return the number of good nodes; an empty tree has none.

What to write

type TreeNode = {val:number;left:TreeNode|null;right:TreeNode|null};

function solve(root: TreeNode | null): number

Input
root = {"val":3,"left":{"val":1,"left":{"val":3,"left":null,"right":null},"right":null},"right":{"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}

Output
4

Input
root = {"val":3,"left":{"val":3,"left":{"val":4,"left":null,"right":null},"right":{"val":2,"left":null,"right":null}},"right":null}

Output
3

Constraints

Nodes use {val, left, right}.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Whether a node is good depends only on the nodes above it on its own path, never on nodes beside it or below it. Values can be negative, and a node that only ties with a value above it is still good.

2. Hint 2: Ask a smaller question

   You are standing on a node and want to decide whether it is good. Do you need the whole list of values above it, or is one number about that list enough? Which number?

3. Hint 3: Name the pattern

   A rule about the nodes above a node is the signal. Write a function that handles one node and calls itself on each child, with an extra argument: the largest value above that node. Each node compares itself with that value and passes the updated value on. Carrying information from parent to children is preorder tree recursion. Read the lesson on preorder tree recursion.

4. Hint 4: State the invariant

   When a call starts on a node, the number it was given is the largest value above that node on its path. So the node is good exactly when its own value is at least that number.

5. Hint 5: Sketch the pseudocode

   visit(node, highest): if the node is missing, return 0. Set good to 1 if the node's value is at least highest, otherwise to 0. Replace highest by the larger of highest and the node's value. Return good + visit(left child, highest) + visit(right child, highest). Start with visit(root, minus infinity), a value below every number.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Carry the largest value on the current root-to-node path into each recursive call.

The slow way

For every node, list the values on its path from the root and compare the node with each one. It is correct, but the same stretches of path are checked over and over. In a tree that is one long chain of n nodes, the paths add up to about n × n / 2 values.

The insight

A node does not need the whole list of values above it, only the largest one. That single number is easy to keep up to date on the way down: for a child, it is the larger of its parent's number and the parent's own value.

Step by step

1. A missing node adds nothing to the count. This is where the recursion stops. Returning 0 lets the parent's sum treat a missing child like any other child.
2. A node is good when no value above it on its path is larger. The number handed down is the largest value above this node. Being at least that large means no node above it is larger, and a tie still counts.
3. Update the largest value on the path to include this node. For this node's children the path is one node longer. Its largest value is the old one or this node's value, whichever is bigger.
4. Count this node if it is good, plus the good nodes under it. Each child counts the good nodes at and below itself, using the updated number. Adding this node's 1 or 0 covers every node from here down exactly once.
5. Start at the root with nothing above it. No value is above the root, so it gets minus infinity, a number below every value. The root then always passes the test, as the definition says.

The same numbered steps are the comments in each solution.

function solve(root) {
  function visit(node, highest) {
    // 1. A missing node adds nothing to the count
    if (!node) return 0;
    // 2. A node is good when no value above it on its path is larger
    const good = node.val >= highest ? 1 : 0;
    // 3. Update the largest value on the path to include this node
    highest = Math.max(highest, node.val);
    // 4. Count this node if it is good, plus the good nodes under it
    return good + visit(node.left, highest) + visit(node.right, highest);
  }
  // 5. Start at the root with nothing above it
  return visit(root, -Infinity);
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(root: TreeNode | null): number {
  function visit(node: TreeNode | null, highest: number): number {
    // 1. A missing node adds nothing to the count
    if (!node) return 0;
    // 2. A node is good when no value above it on its path is larger
    const good = node.val >= highest ? 1 : 0;
    // 3. Update the largest value on the path to include this node
    highest = Math.max(highest, node.val);
    // 4. Count this node if it is good, plus the good nodes under it
    return good + visit(node.left, highest) + visit(node.right, highest);
  }
  // 5. Start at the root with nothing above it
  return visit(root, -Infinity);
}

def solve(root):
    def visit(node, highest):
        # 1. A missing node adds nothing to the count
        if node is None:
            return 0
        # 2. A node is good when no value above it on its path is larger
        good = 1 if node.val >= highest else 0
        # 3. Update the largest value on the path to include this node
        highest = max(highest, node.val)
        # 4. Count this node if it is good, plus the good nodes under it
        return good + visit(node.left, highest) + visit(node.right, highest)

    # 5. Start at the root with nothing above it
    return visit(root, float("-inf"))

Example 1, traced

Input
root = {"val":3,"left":{"val":1,"left":{"val":3,"left":null,"right":null},"right":null},"right":{"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}

Output
4

Why it works

The number a call receives is always the largest value above its node: the root gets minus infinity, and every call passes down the larger of what it got and its own value. So each node is tested against exactly its own path, once, and the results are added up.

Time and space

Time O(n), extra space O(h). Every node is visited once and does one comparison and one update: O(n) time. The unfinished calls lie along the path from the root to the current node, at most about h of them, where the height h counts the nodes on the tree's longest path down: O(h) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Test with "at least", not "greater than". A node that ties with the largest value above it is good. With a strict test, example 1 returns 3 instead of 4.
• Do not start the largest value at 0. Values can be negative, and a root of -1 would fail its own test. Start below every possible value.
• Pass the largest value down as an argument. A single shared variable keeps a large value from the left side and applies it on the right: a root 3 with children 5 and 4 gives 2 instead of 3.

Pattern

Preorder tree recursion. Builds on Maximum Depth of Binary Tree and Binary Tree Right Side View.

Keep going