Builds on Bottom-Up DFS, which you haven’t finished yet.
Preorder DFS (Top-Down Recursion)
You're given a binary tree root. Call a node X good when no node on the path from the root down to X has a value greater than X's own value.
Count how many nodes in the tree qualify as good.
Top-Down DFS
Root ➔ Preorder Argument Passing ➔ Descendant Evaluation| 1 | from typing import Callable, Optional, TypeVar |
| 2 | |
| 3 | S = TypeVar("S") |
| 4 | R = TypeVar("R") |
| 5 | |
| 6 | class TreeNode: |
| 7 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 8 | self.val = val |
| 9 | self.left = left |
| 10 | self.right = right |
| 11 | |
| 12 | |
| 13 | def top_down(root: Optional[TreeNode], start: S, next_state: Callable[[S, TreeNode], S], visit: Callable[[S, TreeNode], R], combine: Callable[[R, R, R], R], empty: R) -> R: |
| 14 | """Top-Down DFS: combine visit(state, node) over every node, where state describes |
| 15 | the path above node. |
| 16 | start is the state above the root. next_state(state, node) is the state handed to |
| 17 | node's children. |
| 18 | combine(here, left, right) joins a node's own result with its subtrees' results, for |
| 19 | example a sum or a max. |
| 20 | empty is the result of an empty subtree. |
| 21 | Precondition: every node is visited, so the template cannot remove nodes from the |
| 22 | tree. |
| 23 | N = number of nodes. H = height. T = the cost of one next_state, visit or combine |
| 24 | call. |
| 25 | Time: O(N * T) | Space: O(H) recursion stack |
| 26 | """ |
| 27 | def dfs(node: Optional[TreeNode], state: S) -> R: |
| 28 | if not node: |
| 29 | return empty # Empty subtree: the neutral result |
| 30 | |
| 31 | here = visit(state, node) # Decide with the state passed down |
| 32 | child_state = next_state(state, node) # Update the state for the children only |
| 33 | |
| 34 | return combine(here, dfs(node.left, child_state), dfs(node.right, child_state)) |
| 35 | |
| 36 | return dfs(root, start) |
max_so_far always equals the largest value on the path from the root down to the parent of node.A node's answer depends on what lies above it, so pass that knowledge down as an argument (max_so_far) instead of searching back up the tree. Each call decides using only its argument and node.val, then hands the updated state (new_max) to both children; because arguments belong to one call, siblings never see each other's changes. Start the state at -inf, so the root counts as good without a special case.
See it run
Top-down DFS (Preorder), step by step
max_so_far -infgood so far 0answer not yet
Each circle is a tree node. The value max_so_far travels down the edges, from parent to child, as a call argument. The list under the tree shows what each node received.
visitingthe call that is running nowgooda node whose value is at least max_so_far, so it is countednot gooda node with a value below max_so_farpassed downthe edge a max_so_far argument travels along, to the child
Call dfs on the root 3 with max_so_far = -inf. The root has no ancestors, so it starts with the smallest possible value.
Gotcha 1 of 4
- The trap
Gotcha 1: Starting
max_so_farat0instead of-infMistakereturn dfs(root, 0)Fixreturn dfs(root, float('-inf'))What happens: The root has no ancestors, so it is always a good node. Node values can be negative. With a start of
0, a negative root failsnode.val >= max_so_far, so it is not counted. Starting at-inf, or atroot.val, makes the root count.Example: root = [-1,-2,-3]Mistake: returns 0Fix: returns 1
- A node's answer comes from what its subtrees hold, as in Balanced Binary Tree (LC 110): nothing above the node changes it. See Bottom-Up DFS
- The output is the list of whole root-to-leaf paths, as in Path Sum II (LC 113), not a count or a yes/no for each node. See Root-to-Leaf Paths
Deep Dive
Why an argument can carry the whole path above a node
A node is good when its value is at least every value on the path from the root down to it. To check that, a call needs the largest value above it. Searching back up the tree is not possible, because a node has no link to its parent. So the parent sends the largest value down, as the argument max_so_far.
The call on the root receives max_so_far = -inf. It has no ancestors, so no value can be larger. Each call checks node.val >= max_so_far, then builds new_max = max(max_so_far, node.val). It passes new_max to both children. This makes the invariant true for every call: max_so_far is the largest value on the path from the root to the parent of node.
Take root = [3, 1, 4, 3, null, 1, 5]. The calls in order receive these values: node 3 gets -inf and is good. Node 1 gets 3 and is not good. The next node 3 gets 3 and is good, because 3 >= 3. Node 4 gets 3 and is good. Node 1 gets 4 and is not good. Node 5 gets 4 and is good. The good nodes are 3, 3, 4 and 5, so the answer is 4.
Information flows down: the argument, not a return value
This card is the second way information can travel in a tree recursion. The information goes down, from parent to children, in an argument. The card Bottom-Up DFS is the first way: information goes up, from children to parent, in a return value.
The two ways answer different questions. Look at the same subtree, a single node with value 3, in two trees: [5, 3] and [1, 3]. The subtree is identical. In [5, 3] the node 3 is not good, and the answer is 1. In [1, 3] the node 3 is good, and the answer is 2. The subtree cannot tell the verdict. Only the path above can. That is why the value must come down as an argument.
The call still returns a number. Here it is the count of good nodes in the subtree, and the parent adds the two counts to its own. But the number that makes the decision is the argument. A short test: if the decision at a node needs something from above it, such as a running maximum, a remaining sum or a depth, use this card. If the decision needs something from below it, use Bottom-Up DFS.
Many problems use both. Binary Tree Maximum Path Sum (LC 124) returns values up. Validate Binary Search Tree (LC 98) passes a lower and an upper bound down. The order of the calls tells you which way a value travels: an argument is fixed before the children run, and a return value exists only after they finish.
The trap: one shared variable instead of an argument
An argument belongs to one call. Each call has its own copy, so a change made inside a call is invisible to the calls next to it. This is what makes the pass-down correct.
A shared variable breaks it. Suppose the code keeps one max_so_far outside the function and updates it with max_so_far = max(max_so_far, node.val). The left subtree raises the value. The raised value is still there when the right subtree starts. So a node on the right is compared with values that are not its ancestors.
Take root = [1, 5, 2]. The correct code gives 3: the root 1 is good, 5 is good because 5 >= 1, and 2 is good because its only ancestor is 1. The shared variable code gives 2. After the left child 5 raises the variable to 5, the right child 2 is compared with 5 and fails.
A second trap is the start value. The root must count as good. With float('-inf') it does. With 0, a root of -1 fails -1 >= 0. For root = [-1, -2, -3] the correct answer is 1 and the code that starts at 0 returns 0.
The cost, and how it differs from Bottom-Up DFS
Every node is visited once, and each visit does constant work: one comparison and one max. The time is O(N). The space is O(H) for the recursion stack, where H is the height. The argument adds one number per call, so it does not change the order of the space.
The state can be more than one number. Sum Root to Leaf Numbers (LC 129) passes cur * 10 + node.val down. Path Sum (LC 112) passes the remaining target. Each call still receives one value and passes an updated value to both children.
Be careful about where the answer is read. Path Sum (LC 112) counts only paths that end at a leaf. A node with one child has one empty side, and a check at the empty side accepts a path that stops at that node. For root = [1, 2] with targetSum = 1, the correct answer is False. The check must happen at a node that has no children.
Compare with Bottom-Up DFS. There, a subtree is enough, and the parent waits for the children. Here, the path above is needed, and the parent speaks first. If the question wants whole paths as output, as in Path Sum II (LC 113), the argument is also a growing list, and the card Root-to-Leaf Paths is the better fit.
60-Second Pitch
"A node is good when no ancestor is larger, so the decision depends on the path above the node. I pass that information down as an argument. My function is dfs(node, max_so_far). The root gets -inf. A node is good when node.val >= max_so_far. Then I compute new_max = max(max_so_far, node.val) and pass it to both children. I return the node's own count plus the counts of the two subtrees. The argument belongs to one call, so the left subtree cannot change what the right subtree sees. A shared variable would break this. Each node is visited once, so the time is O(N). The space is O(H) for the recursion stack."
Common Questions
- Why do you pass
max_so_faras an argument and not keep it in a variable outside the function? An argument is a separate copy for each call. After the left subtree finishes, the right subtree still receives the value from the parent. A shared variable keeps the changes of the left subtree. In
[1, 5, 2]that gives 2 instead of 3, because the node 2 is compared with 5, which is not its ancestor.- Why start with
-infand not 0? The root has no ancestors, so it must always count. Node values can be negative. With a start of 0, the root of
[-1, -2, -3]fails-1 >= 0and the code returns 0 instead of 1.-infis smaller than every value, so the root always passes.- What are the time and space complexity?
O(N)time, because each node is visited once with constant work. O(H) space for the recursion stack, whereHis the height. That is about log N for a balanced tree and N for a chain.- How do you know whether to pass information down or return it up?
Ask what the answer for a node needs. If it needs only its subtrees, return it up. If it needs the path above, pass it down. Moving the same subtree to another tree changes the answer in the second case, and that is the sign. Maximum Depth of Binary Tree (LC 104) is the first case. Count Good Nodes in Binary Tree (LC 1448) is the second.
- What changes if the state has more than one value, as in Validate Binary Search Tree (LC 98)?
The argument becomes a pair, such as
(low, high). Each call checkslow < node.val < high. It passes(low, node.val)to the left child and(node.val, high)to the right child. The recursion shape is the same. Onlynext_statechanges.
SWE Reasoning
Spot it
- Whether a node counts depends on the path from the root to it: a running maximum, a remaining sum, a depth or a count of ancestors.
- The same subtree can have a different answer in a different tree, because the answer depends on what lies above it.
- The wording says "on the path from the root", "greater than all ancestors", "root to leaf" or "so far".
- The state can be written as one small value, such as a number or a pair, that each node can update for its children.
- A node has no link to its parent, so searching upward is not possible. The information must come down.
The invariant, step by step
- The call on the root receives a start value that fits "no ancestors":
-inffor a running maximum. - Each call decides about
nodeusing only its argument andnode.val. Here, it counts the node whennode.val >= max_so_far. - The call then builds
new_max = max(max_so_far, node.val). This is the largest value on the path from the root throughnode. - It passes
new_maxas an argument to both children. Each child receives its own copy, so the children do not affect each other. - So for every call,
max_so_faris the largest value from the root down to the parent ofnode. The result is the count of the node plus the counts from both subtrees.
Traps
- A shared variable. One
max_so_faroutside the function lets the left subtree change what the right subtree sees. Use a new argument for each child. - A start value of 0. A root with a negative value is not counted. Start at
-inf, or at the root's value. - Checking at an empty child. For path problems, a node with one child also has one empty side. Check at a node that has no children.
- Counting a leaf twice. A leaf has two empty children. Returning the number at the empty child adds the leaf's number twice.
- Using this card when the subtree is enough. If the answer depends only on the subtrees, use Bottom-Up DFS. It needs no argument.
Practice
Builds on Bottom-Up DFS, which you haven’t finished yet.
Preorder DFS (Top-Down Recursion)
You're given a binary tree root. Call a node X good when no node on the path from the root down to X has a value greater than X's own value.
Count how many nodes in the tree qualify as good.
Top-Down DFS
Root ➔ Preorder Argument Passing ➔ Descendant Evaluation| 1 | from typing import Callable, Optional, TypeVar |
| 2 | |
| 3 | S = TypeVar("S") |
| 4 | R = TypeVar("R") |
| 5 | |
| 6 | class TreeNode: |
| 7 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 8 | self.val = val |
| 9 | self.left = left |
| 10 | self.right = right |
| 11 | |
| 12 | |
| 13 | def top_down(root: Optional[TreeNode], start: S, next_state: Callable[[S, TreeNode], S], visit: Callable[[S, TreeNode], R], combine: Callable[[R, R, R], R], empty: R) -> R: |
| 14 | """Top-Down DFS: combine visit(state, node) over every node, where state describes |
| 15 | the path above node. |
| 16 | start is the state above the root. next_state(state, node) is the state handed to |
| 17 | node's children. |
| 18 | combine(here, left, right) joins a node's own result with its subtrees' results, for |
| 19 | example a sum or a max. |
| 20 | empty is the result of an empty subtree. |
| 21 | Precondition: every node is visited, so the template cannot remove nodes from the |
| 22 | tree. |
| 23 | N = number of nodes. H = height. T = the cost of one next_state, visit or combine |
| 24 | call. |
| 25 | Time: O(N * T) | Space: O(H) recursion stack |
| 26 | """ |
| 27 | def dfs(node: Optional[TreeNode], state: S) -> R: |
| 28 | if not node: |
| 29 | return empty # Empty subtree: the neutral result |
| 30 | |
| 31 | here = visit(state, node) # Decide with the state passed down |
| 32 | child_state = next_state(state, node) # Update the state for the children only |
| 33 | |
| 34 | return combine(here, dfs(node.left, child_state), dfs(node.right, child_state)) |
| 35 | |
| 36 | return dfs(root, start) |
max_so_far always equals the largest value on the path from the root down to the parent of node.A node's answer depends on what lies above it, so pass that knowledge down as an argument (max_so_far) instead of searching back up the tree. Each call decides using only its argument and node.val, then hands the updated state (new_max) to both children; because arguments belong to one call, siblings never see each other's changes. Start the state at -inf, so the root counts as good without a special case.
See it run
Top-down DFS (Preorder), step by step
max_so_far -infgood so far 0answer not yet
Each circle is a tree node. The value max_so_far travels down the edges, from parent to child, as a call argument. The list under the tree shows what each node received.
visitingthe call that is running nowgooda node whose value is at least max_so_far, so it is countednot gooda node with a value below max_so_farpassed downthe edge a max_so_far argument travels along, to the child
Call dfs on the root 3 with max_so_far = -inf. The root has no ancestors, so it starts with the smallest possible value.
Gotcha 1 of 4
- The trap
Gotcha 1: Starting
max_so_farat0instead of-infMistakereturn dfs(root, 0)Fixreturn dfs(root, float('-inf'))What happens: The root has no ancestors, so it is always a good node. Node values can be negative. With a start of
0, a negative root failsnode.val >= max_so_far, so it is not counted. Starting at-inf, or atroot.val, makes the root count.Example: root = [-1,-2,-3]Mistake: returns 0Fix: returns 1
- A node's answer comes from what its subtrees hold, as in Balanced Binary Tree (LC 110): nothing above the node changes it. See Bottom-Up DFS
- The output is the list of whole root-to-leaf paths, as in Path Sum II (LC 113), not a count or a yes/no for each node. See Root-to-Leaf Paths
Deep Dive
Why an argument can carry the whole path above a node
A node is good when its value is at least every value on the path from the root down to it. To check that, a call needs the largest value above it. Searching back up the tree is not possible, because a node has no link to its parent. So the parent sends the largest value down, as the argument max_so_far.
The call on the root receives max_so_far = -inf. It has no ancestors, so no value can be larger. Each call checks node.val >= max_so_far, then builds new_max = max(max_so_far, node.val). It passes new_max to both children. This makes the invariant true for every call: max_so_far is the largest value on the path from the root to the parent of node.
Take root = [3, 1, 4, 3, null, 1, 5]. The calls in order receive these values: node 3 gets -inf and is good. Node 1 gets 3 and is not good. The next node 3 gets 3 and is good, because 3 >= 3. Node 4 gets 3 and is good. Node 1 gets 4 and is not good. Node 5 gets 4 and is good. The good nodes are 3, 3, 4 and 5, so the answer is 4.
Information flows down: the argument, not a return value
This card is the second way information can travel in a tree recursion. The information goes down, from parent to children, in an argument. The card Bottom-Up DFS is the first way: information goes up, from children to parent, in a return value.
The two ways answer different questions. Look at the same subtree, a single node with value 3, in two trees: [5, 3] and [1, 3]. The subtree is identical. In [5, 3] the node 3 is not good, and the answer is 1. In [1, 3] the node 3 is good, and the answer is 2. The subtree cannot tell the verdict. Only the path above can. That is why the value must come down as an argument.
The call still returns a number. Here it is the count of good nodes in the subtree, and the parent adds the two counts to its own. But the number that makes the decision is the argument. A short test: if the decision at a node needs something from above it, such as a running maximum, a remaining sum or a depth, use this card. If the decision needs something from below it, use Bottom-Up DFS.
Many problems use both. Binary Tree Maximum Path Sum (LC 124) returns values up. Validate Binary Search Tree (LC 98) passes a lower and an upper bound down. The order of the calls tells you which way a value travels: an argument is fixed before the children run, and a return value exists only after they finish.
The trap: one shared variable instead of an argument
An argument belongs to one call. Each call has its own copy, so a change made inside a call is invisible to the calls next to it. This is what makes the pass-down correct.
A shared variable breaks it. Suppose the code keeps one max_so_far outside the function and updates it with max_so_far = max(max_so_far, node.val). The left subtree raises the value. The raised value is still there when the right subtree starts. So a node on the right is compared with values that are not its ancestors.
Take root = [1, 5, 2]. The correct code gives 3: the root 1 is good, 5 is good because 5 >= 1, and 2 is good because its only ancestor is 1. The shared variable code gives 2. After the left child 5 raises the variable to 5, the right child 2 is compared with 5 and fails.
A second trap is the start value. The root must count as good. With float('-inf') it does. With 0, a root of -1 fails -1 >= 0. For root = [-1, -2, -3] the correct answer is 1 and the code that starts at 0 returns 0.
The cost, and how it differs from Bottom-Up DFS
Every node is visited once, and each visit does constant work: one comparison and one max. The time is O(N). The space is O(H) for the recursion stack, where H is the height. The argument adds one number per call, so it does not change the order of the space.
The state can be more than one number. Sum Root to Leaf Numbers (LC 129) passes cur * 10 + node.val down. Path Sum (LC 112) passes the remaining target. Each call still receives one value and passes an updated value to both children.
Be careful about where the answer is read. Path Sum (LC 112) counts only paths that end at a leaf. A node with one child has one empty side, and a check at the empty side accepts a path that stops at that node. For root = [1, 2] with targetSum = 1, the correct answer is False. The check must happen at a node that has no children.
Compare with Bottom-Up DFS. There, a subtree is enough, and the parent waits for the children. Here, the path above is needed, and the parent speaks first. If the question wants whole paths as output, as in Path Sum II (LC 113), the argument is also a growing list, and the card Root-to-Leaf Paths is the better fit.
60-Second Pitch
"A node is good when no ancestor is larger, so the decision depends on the path above the node. I pass that information down as an argument. My function is dfs(node, max_so_far). The root gets -inf. A node is good when node.val >= max_so_far. Then I compute new_max = max(max_so_far, node.val) and pass it to both children. I return the node's own count plus the counts of the two subtrees. The argument belongs to one call, so the left subtree cannot change what the right subtree sees. A shared variable would break this. Each node is visited once, so the time is O(N). The space is O(H) for the recursion stack."
Common Questions
- Why do you pass
max_so_faras an argument and not keep it in a variable outside the function? An argument is a separate copy for each call. After the left subtree finishes, the right subtree still receives the value from the parent. A shared variable keeps the changes of the left subtree. In
[1, 5, 2]that gives 2 instead of 3, because the node 2 is compared with 5, which is not its ancestor.- Why start with
-infand not 0? The root has no ancestors, so it must always count. Node values can be negative. With a start of 0, the root of
[-1, -2, -3]fails-1 >= 0and the code returns 0 instead of 1.-infis smaller than every value, so the root always passes.- What are the time and space complexity?
O(N)time, because each node is visited once with constant work. O(H) space for the recursion stack, whereHis the height. That is about log N for a balanced tree and N for a chain.- How do you know whether to pass information down or return it up?
Ask what the answer for a node needs. If it needs only its subtrees, return it up. If it needs the path above, pass it down. Moving the same subtree to another tree changes the answer in the second case, and that is the sign. Maximum Depth of Binary Tree (LC 104) is the first case. Count Good Nodes in Binary Tree (LC 1448) is the second.
- What changes if the state has more than one value, as in Validate Binary Search Tree (LC 98)?
The argument becomes a pair, such as
(low, high). Each call checkslow < node.val < high. It passes(low, node.val)to the left child and(node.val, high)to the right child. The recursion shape is the same. Onlynext_statechanges.
SWE Reasoning
Spot it
- Whether a node counts depends on the path from the root to it: a running maximum, a remaining sum, a depth or a count of ancestors.
- The same subtree can have a different answer in a different tree, because the answer depends on what lies above it.
- The wording says "on the path from the root", "greater than all ancestors", "root to leaf" or "so far".
- The state can be written as one small value, such as a number or a pair, that each node can update for its children.
- A node has no link to its parent, so searching upward is not possible. The information must come down.
The invariant, step by step
- The call on the root receives a start value that fits "no ancestors":
-inffor a running maximum. - Each call decides about
nodeusing only its argument andnode.val. Here, it counts the node whennode.val >= max_so_far. - The call then builds
new_max = max(max_so_far, node.val). This is the largest value on the path from the root throughnode. - It passes
new_maxas an argument to both children. Each child receives its own copy, so the children do not affect each other. - So for every call,
max_so_faris the largest value from the root down to the parent ofnode. The result is the count of the node plus the counts from both subtrees.
Traps
- A shared variable. One
max_so_faroutside the function lets the left subtree change what the right subtree sees. Use a new argument for each child. - A start value of 0. A root with a negative value is not counted. Start at
-inf, or at the root's value. - Checking at an empty child. For path problems, a node with one child also has one empty side. Check at a node that has no children.
- Counting a leaf twice. A leaf has two empty children. Returning the number at the empty child adds the leaf's number twice.
- Using this card when the subtree is enough. If the answer depends only on the subtrees, use Bottom-Up DFS. It needs no argument.