FAANGPrep Sprint
Passing Values Down (State)
Learn how to pass information (state) from parents to children in DFS.
Examples
Good nodes are in bold: [3,1,4,3,null,1,5].
Path 3->1->3: Node 3 is good because 3 >= 3.
Path 3->4->5: Node 5 is good because 5 >= 4.
Problem Understanding
We need to count the Good Nodes in a binary tree.
A node is Good if, in the path from the Root to that Node, there are no nodes with a value greater than the node itself.
In simpler terms: Is this node the largest (or equal largest) value we've seen so far on this path?
Algorithm Strategy (Top-Down State)
We use Pre-order DFS (Top-Down) to solve this.
We need to pass the Maximum Value Seen So Far down to children. This 'state' allows each child to decide if it is 'good' without looking back up the tree.
- State:
maxVal(the maximum value encountered on the current path). - Check: If
node.val >= maxVal, the node is Good. Increment count. - Update: New state for children is
max(maxVal, node.val). - Recurse: Call DFS on left and right children with the updated state.
Interactive Visualization
GOOD = NOTHING LARGER ABOVE IT
CALL dfs(root, root.val)
Good so far
0
Answer
—
call stack
No calls in progress
Call dfs(root, 3): the root is compared with itself, so it is always good
Next
dfs(3, maxVal 3): the largest value on the path above is 3
Tree
The largest value on the path above each node arrives as an argument and appears under it. A node at least that large is good and turns green; the new maximum is passed on to both children.