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
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.
Dry Run: [3, 1, 4, 3, null, 1, 5]
| Node | Max So Far | Is Good? (Node >= Max) | New Max (passed down) | Action |
|---|---|---|---|---|
| 3 (Root) | 3 (root.val) | Yes (3 >= 3) | 3 | Count = 1. Recurse L (Max 3) |
| 1 | 3 | No (1 < 3) | 3 | Count = 1. Recurse L (Max 3) |
| 3 (Leaf) | 3 | Yes (3 >= 3) | 3 | Count = 2. Return. |
| 4 | 3 | Yes (4 >= 3) | 4 | Count = 3. Recurse L (Max 4) |
| 1 (Leaf) | 4 | No (1 < 4) | 4 | Count = 3. Return. |
| 5 (Leaf) | 4 | Yes (5 >= 4) | 5 | Count = 4. Return. |
Edge Cases
- Single Node: Always good. Return 1.
- Increasing Path: All nodes good.
- Decreasing Path: Only root is good.
- Negative Values: Logic holds (Max So Far handles negatives correctly).
Solution
DFS passing maxVal down.
Passing Values Down (State) Code
1var goodNodes = function(root) {2 function dfs(node, maxVal) {3 if (!node) return 0;4 const good = node.val >= maxVal ? 1 : 0;5 const newMax = Math.max(maxVal, node.val);6 return good + dfs(node.left, newMax) + dfs(node.right, newMax);7 }89 return dfs(root, root.val);10};