Postorder DFS (Bottom-Up Recursion)
You're handed the root of a binary tree and asked how tall it is: its maximum depth.
The maximum depth counts the nodes on the single longest chain running from the root all the way down to whichever leaf sits farthest away.
Bottom-Up DFS
Leaves ➔ Postorder Child Return ➔ Parent Combine| 1 | from typing import Callable, Optional, TypeVar |
| 2 | |
| 3 | R = TypeVar("R") |
| 4 | |
| 5 | class TreeNode: |
| 6 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 7 | self.val = val |
| 8 | self.left = left |
| 9 | self.right = right |
| 10 | |
| 11 | |
| 12 | def bottom_up(root: Optional[TreeNode], empty: R, combine: Callable[[TreeNode, R, R], R]) -> R: |
| 13 | """Bottom-Up DFS: the answer for the tree at root, built from the answers of its |
| 14 | subtrees. |
| 15 | empty is the answer for an empty subtree. combine(node, left, right) builds node's |
| 16 | answer from its children's answers. |
| 17 | Precondition: a node's answer depends only on the node and on the answers of its two |
| 18 | subtrees. |
| 19 | Same Tree, Symmetric Tree, Merge Two Binary Trees and Subtree of Another Tree walk |
| 20 | two trees at once, so they do not fit. |
| 21 | N = number of nodes. H = height. T = the cost of one combine call. |
| 22 | Time: O(N * T) | Space: O(H) recursion stack |
| 23 | """ |
| 24 | def solve(node: Optional[TreeNode]) -> R: |
| 25 | # 1. Base case: the answer for an empty subtree |
| 26 | if not node: |
| 27 | return empty |
| 28 | |
| 29 | # 2. Divide: solve each subtree on its own |
| 30 | left = solve(node.left) |
| 31 | right = solve(node.right) |
| 32 | |
| 33 | # 3. Combine: this node's answer comes only from its children's answers |
| 34 | return combine(node, left, right) |
| 35 | |
| 36 | return solve(root) |
maxDepth(root) returns the finished answer for the subtree at root, built only from left_depth and right_depth.A node's answer depends only on its subtrees' answers, so call maxDepth on root.left and root.right first and combine the two results on the way back up. Each call returns a finished answer for its own subtree, so the parent never looks deeper than those two numbers, and every node is visited exactly once. The trap is the base case: if not root: return 0 must be the value the combine step expects from an empty subtree. A base case that doesn't fit the combine, such as treating a missing child as a leaf in Minimum Depth of Binary Tree (LC 111), returns wrong answers.
See it run
Bottom-up DFS (Postorder), step by step
returns -answer not yet
Each circle is a tree node. A finished node shows its value, an arrow, and the depth its call returned. The numbers travel up the edges, from child to parent.
callingthe call that has just startedwaitinga call that waits for its childrenreturneda call that has returned its depthvalue upthe edge a returned depth travels along, to the parent
Call maxDepth on the root 3. Each call asks its two children first, then combines their answers.
Gotcha 1 of 4
- The trap
Gotcha 1: Taking
1 + min(left_depth, right_depth)with a missing childMistakereturn 1 + min(left_depth, right_depth)Fixif not root.left or not root.right: return 1 + max(left_depth, right_depth) return 1 + min(left_depth, right_depth)What happens: Minimum Depth of Binary Tree (LC 111) counts nodes down to the nearest leaf. A missing child returns 0 from the base case.
minthen picks that 0, so a node with one child is counted as a leaf. When one child is missing, the depth must come from the other child.Example: Minimum Depth of Binary Tree (LC 111): root = [2,null,3,null,4,null,5,null,6]Mistake: returns 1Fix: returns 5
- Whether a node counts depends on the values above it, as in Count Good Nodes in Binary Tree (LC 1448): its subtrees can't tell you that, only the path from the root can. See Top-Down DFS
- The best path may bend at any node and need not touch the root, as in Binary Tree Maximum Path Sum (LC 124), so the value the root returns is not the answer. See Tree Diameter DP
Deep Dive
Why a call can trust the answers of its children
maxDepth(root) is defined by one sentence: it returns the depth of the tree that starts at root. The code only has to keep that sentence true for one call, and the sentence then holds for every call.
An empty tree has depth 0, so the base case if not root: return 0 is true. For a real node, the two recursive calls are on smaller trees. By the same sentence, left_depth and right_depth are the true depths of those two trees. The deepest path through the node goes down one side, so its depth is 1 + max(left_depth, right_depth). The node adds 1 for itself.
Take root = [3, 9, 20, null, null, 15, 7]. The calls on 9, 15 and 7 are leaves, and each returns 1 + max(0, 0) = 1. The call on 20 receives 1 and 1 and returns 2. The call on 3 receives 1 and 2 and returns 3. That is the answer. The call on 3 never looks at 15 or 7 itself. It uses only the two numbers its children returned.
Information flows up: the return value, not an argument
Every DFS card on this pattern answers one question: which way does the information travel? There are two ways. The information travels up, from children to parent, in a return value. Or it travels down, from parent to children, in an argument.
This card is the first way. maxDepth(node) has no argument except the node. The parent learns about its subtrees only from what the calls return. Because of that, the order is fixed: both child calls must finish before the parent can compute anything. This order is called postorder.
Count Good Nodes in Binary Tree (LC 1448) is the second way. The question "is this node good?" depends on the nodes above it, so the nodes above it must send a value down as an argument. The card Top-Down DFS teaches that way.
A test for your own problem: ask whether a node's answer changes when you move the same subtree to a different place in the tree. If the answer stays the same, the subtree is enough, and this card applies. If the answer changes, the answer depends on what lies above the node, and you must pass something down. Binary Tree Maximum Path Sum (LC 124) and Distribute Coins in Binary Tree (LC 979) are built on this card. They return a number up, and they change what the number means.
The trap: the base case must fit the combine step
The base case returns the answer for an empty tree. The combine step then treats that value like any other child answer. If the value does not mean the same thing in the combine, the answer is wrong.
Minimum Depth of Binary Tree (LC 111) shows it. Copying maxDepth and replacing max with min gives 1 + min(left_depth, right_depth). For root = [2, null, 3, null, 4, null, 5, null, 6], the node 2 has no left child. The empty left side returns 0, and min(0, 4) is 0. So the code returns 1 for a tree whose nearest leaf is 5 nodes deep. The correct answer is 5.
The reason is that an empty child is not a leaf. A path can end only at a leaf, which has no children at all. The fix is a check in the combine step: when root.left or root.right is missing, use 1 + max(left_depth, right_depth), so the empty side is ignored. With the check, the same tree returns 5.
The same question applies to every problem on this card. Before writing the combine, ask what an empty subtree must return so that the combine ignores it. For a sum or a depth with max, 0 works. For a depth with min, it does not.
The cost, and returning two facts in one call
Each node is visited once, and each visit does constant work. The time is O(N) for a tree with N nodes. The space is O(H), where H is the height of the tree, because one call waits on the stack for each level. For a balanced tree, H is about log N. For a chain, H is N.
A chain is the danger. Python stops at about 1000 nested calls by default. A chain of 10,000 nodes raises RecursionError unless you raise the limit with sys.setrecursionlimit or walk the tree with an explicit stack.
Sometimes one call must return two facts. Balanced Binary Tree (LC 110) needs the height of each subtree and whether the subtree is balanced. A separate height function called at every node measures the same subtrees many times. On a complete tree with 15 nodes, it makes 98 calls to height. A single function that returns the height, or -1 when a subtree is unbalanced, makes 31 calls in total. The extra fact travels in the same return value, so there is no second walk.
60-Second Pitch
"The depth of a tree is built from the depths of its two subtrees, so I use a bottom-up recursion. maxDepth(root) returns the depth of the tree at root. An empty tree returns 0. For any other node, I call it on the left child and the right child first, and I return 1 + max(left_depth, right_depth). It is correct because each call can trust the two numbers it receives. Those numbers are the true depths of smaller trees, and the node adds 1 for itself. Each node is visited once, so the time is O(N). The space is O(H) for the recursion stack. For a chain of 10,000 nodes, I would use an explicit stack or raise the recursion limit."
Common Questions
- What is the difference between passing information up and passing it down?
Information goes up in a return value. A parent learns about its subtrees from what the child calls return, so the child calls run first (postorder). Information goes down in an argument. A child learns about the path above it from what its parent passes, so the parent decides first (preorder). Maximum Depth of Binary Tree (LC 104) goes up. Count Good Nodes in Binary Tree (LC 1448) goes down.
- Why does Minimum Depth of Binary Tree (LC 111) fail with
min? An empty child returns 0, and 0 is smaller than any real depth, so
minpicks it. A node with one child is then treated as a leaf. In[2, null, 3, null, 4, null, 5, null, 6]the code returns 1 and not 5. The fix is to use the depth of the child that exists when the other child is missing.- 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 would you avoid the recursion limit on a very deep tree?
Walk the tree level by level with a queue and count the levels, which needs no recursion. Or use an explicit stack that holds
(node, depth)pairs and keep the largest depth. Raisingsys.setrecursionlimitalso works for a depth near 10,000, but each call still uses stack memory.- Balanced Binary Tree (LC 110) needs the height and the balance. How do you get both in
O(N)? Return one value. The call returns the height of the subtree, or -1 when the subtree is not balanced. If a child returns -1, the parent returns -1 at once. Otherwise it compares the two heights and returns
1 + max(left, right). Each node is visited once.
SWE Reasoning
Spot it
- The answer for a node follows from the answers of its left and right subtrees: height, depth, size, balance, lowest common ancestor.
- Moving the same subtree to another place in the tree does not change its answer.
- The wording asks for one number or one yes/no for the whole tree, built from smaller trees.
- You can state in one sentence what
solve(node)returns for the subtree atnode. - Nothing above a node changes what the node should report. If something does, use Top-Down DFS instead.
The invariant, step by step
- Define in one sentence what
solve(node)returns: the finished answer for the subtree atnode. - The base case returns the answer for an empty subtree. It is true by definition, and the value must fit the combine step.
- For a real node, the two child calls run first. By the sentence in step 1, they return the finished answers for the left and right subtrees.
- The combine step builds the answer for this node from those two answers and from
nodeitself. It does not look any deeper. - So the sentence is true for this call, and it is true for every call. The call on the root returns the answer for the whole tree.
Traps
- A base case that does not fit the combine. With
min, an empty child returns 0 and wins. Minimum Depth of Binary Tree (LC 111) needs a check for a missing child. - Two walks for two facts. Calling a separate
heightat every node repeats work. Return both facts from one call, for example -1 for an unbalanced subtree. - A deep chain. A tree with 10,000 nodes in a chain can pass Python's default limit of about 1000 nested calls.
- Returning a node instead of a value. Lowest Common Ancestor of a Binary Tree (LC 236) returns the node found, so a call on
porqmust return that node itself. - Using this card when the answer depends on the ancestors. Then the information must go down as an argument, not up as a return value.
Practice
Postorder DFS (Bottom-Up Recursion)
You're handed the root of a binary tree and asked how tall it is: its maximum depth.
The maximum depth counts the nodes on the single longest chain running from the root all the way down to whichever leaf sits farthest away.
Bottom-Up DFS
Leaves ➔ Postorder Child Return ➔ Parent Combine| 1 | from typing import Callable, Optional, TypeVar |
| 2 | |
| 3 | R = TypeVar("R") |
| 4 | |
| 5 | class TreeNode: |
| 6 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 7 | self.val = val |
| 8 | self.left = left |
| 9 | self.right = right |
| 10 | |
| 11 | |
| 12 | def bottom_up(root: Optional[TreeNode], empty: R, combine: Callable[[TreeNode, R, R], R]) -> R: |
| 13 | """Bottom-Up DFS: the answer for the tree at root, built from the answers of its |
| 14 | subtrees. |
| 15 | empty is the answer for an empty subtree. combine(node, left, right) builds node's |
| 16 | answer from its children's answers. |
| 17 | Precondition: a node's answer depends only on the node and on the answers of its two |
| 18 | subtrees. |
| 19 | Same Tree, Symmetric Tree, Merge Two Binary Trees and Subtree of Another Tree walk |
| 20 | two trees at once, so they do not fit. |
| 21 | N = number of nodes. H = height. T = the cost of one combine call. |
| 22 | Time: O(N * T) | Space: O(H) recursion stack |
| 23 | """ |
| 24 | def solve(node: Optional[TreeNode]) -> R: |
| 25 | # 1. Base case: the answer for an empty subtree |
| 26 | if not node: |
| 27 | return empty |
| 28 | |
| 29 | # 2. Divide: solve each subtree on its own |
| 30 | left = solve(node.left) |
| 31 | right = solve(node.right) |
| 32 | |
| 33 | # 3. Combine: this node's answer comes only from its children's answers |
| 34 | return combine(node, left, right) |
| 35 | |
| 36 | return solve(root) |
maxDepth(root) returns the finished answer for the subtree at root, built only from left_depth and right_depth.A node's answer depends only on its subtrees' answers, so call maxDepth on root.left and root.right first and combine the two results on the way back up. Each call returns a finished answer for its own subtree, so the parent never looks deeper than those two numbers, and every node is visited exactly once. The trap is the base case: if not root: return 0 must be the value the combine step expects from an empty subtree. A base case that doesn't fit the combine, such as treating a missing child as a leaf in Minimum Depth of Binary Tree (LC 111), returns wrong answers.
See it run
Bottom-up DFS (Postorder), step by step
returns -answer not yet
Each circle is a tree node. A finished node shows its value, an arrow, and the depth its call returned. The numbers travel up the edges, from child to parent.
callingthe call that has just startedwaitinga call that waits for its childrenreturneda call that has returned its depthvalue upthe edge a returned depth travels along, to the parent
Call maxDepth on the root 3. Each call asks its two children first, then combines their answers.
Gotcha 1 of 4
- The trap
Gotcha 1: Taking
1 + min(left_depth, right_depth)with a missing childMistakereturn 1 + min(left_depth, right_depth)Fixif not root.left or not root.right: return 1 + max(left_depth, right_depth) return 1 + min(left_depth, right_depth)What happens: Minimum Depth of Binary Tree (LC 111) counts nodes down to the nearest leaf. A missing child returns 0 from the base case.
minthen picks that 0, so a node with one child is counted as a leaf. When one child is missing, the depth must come from the other child.Example: Minimum Depth of Binary Tree (LC 111): root = [2,null,3,null,4,null,5,null,6]Mistake: returns 1Fix: returns 5
- Whether a node counts depends on the values above it, as in Count Good Nodes in Binary Tree (LC 1448): its subtrees can't tell you that, only the path from the root can. See Top-Down DFS
- The best path may bend at any node and need not touch the root, as in Binary Tree Maximum Path Sum (LC 124), so the value the root returns is not the answer. See Tree Diameter DP
Deep Dive
Why a call can trust the answers of its children
maxDepth(root) is defined by one sentence: it returns the depth of the tree that starts at root. The code only has to keep that sentence true for one call, and the sentence then holds for every call.
An empty tree has depth 0, so the base case if not root: return 0 is true. For a real node, the two recursive calls are on smaller trees. By the same sentence, left_depth and right_depth are the true depths of those two trees. The deepest path through the node goes down one side, so its depth is 1 + max(left_depth, right_depth). The node adds 1 for itself.
Take root = [3, 9, 20, null, null, 15, 7]. The calls on 9, 15 and 7 are leaves, and each returns 1 + max(0, 0) = 1. The call on 20 receives 1 and 1 and returns 2. The call on 3 receives 1 and 2 and returns 3. That is the answer. The call on 3 never looks at 15 or 7 itself. It uses only the two numbers its children returned.
Information flows up: the return value, not an argument
Every DFS card on this pattern answers one question: which way does the information travel? There are two ways. The information travels up, from children to parent, in a return value. Or it travels down, from parent to children, in an argument.
This card is the first way. maxDepth(node) has no argument except the node. The parent learns about its subtrees only from what the calls return. Because of that, the order is fixed: both child calls must finish before the parent can compute anything. This order is called postorder.
Count Good Nodes in Binary Tree (LC 1448) is the second way. The question "is this node good?" depends on the nodes above it, so the nodes above it must send a value down as an argument. The card Top-Down DFS teaches that way.
A test for your own problem: ask whether a node's answer changes when you move the same subtree to a different place in the tree. If the answer stays the same, the subtree is enough, and this card applies. If the answer changes, the answer depends on what lies above the node, and you must pass something down. Binary Tree Maximum Path Sum (LC 124) and Distribute Coins in Binary Tree (LC 979) are built on this card. They return a number up, and they change what the number means.
The trap: the base case must fit the combine step
The base case returns the answer for an empty tree. The combine step then treats that value like any other child answer. If the value does not mean the same thing in the combine, the answer is wrong.
Minimum Depth of Binary Tree (LC 111) shows it. Copying maxDepth and replacing max with min gives 1 + min(left_depth, right_depth). For root = [2, null, 3, null, 4, null, 5, null, 6], the node 2 has no left child. The empty left side returns 0, and min(0, 4) is 0. So the code returns 1 for a tree whose nearest leaf is 5 nodes deep. The correct answer is 5.
The reason is that an empty child is not a leaf. A path can end only at a leaf, which has no children at all. The fix is a check in the combine step: when root.left or root.right is missing, use 1 + max(left_depth, right_depth), so the empty side is ignored. With the check, the same tree returns 5.
The same question applies to every problem on this card. Before writing the combine, ask what an empty subtree must return so that the combine ignores it. For a sum or a depth with max, 0 works. For a depth with min, it does not.
The cost, and returning two facts in one call
Each node is visited once, and each visit does constant work. The time is O(N) for a tree with N nodes. The space is O(H), where H is the height of the tree, because one call waits on the stack for each level. For a balanced tree, H is about log N. For a chain, H is N.
A chain is the danger. Python stops at about 1000 nested calls by default. A chain of 10,000 nodes raises RecursionError unless you raise the limit with sys.setrecursionlimit or walk the tree with an explicit stack.
Sometimes one call must return two facts. Balanced Binary Tree (LC 110) needs the height of each subtree and whether the subtree is balanced. A separate height function called at every node measures the same subtrees many times. On a complete tree with 15 nodes, it makes 98 calls to height. A single function that returns the height, or -1 when a subtree is unbalanced, makes 31 calls in total. The extra fact travels in the same return value, so there is no second walk.
60-Second Pitch
"The depth of a tree is built from the depths of its two subtrees, so I use a bottom-up recursion. maxDepth(root) returns the depth of the tree at root. An empty tree returns 0. For any other node, I call it on the left child and the right child first, and I return 1 + max(left_depth, right_depth). It is correct because each call can trust the two numbers it receives. Those numbers are the true depths of smaller trees, and the node adds 1 for itself. Each node is visited once, so the time is O(N). The space is O(H) for the recursion stack. For a chain of 10,000 nodes, I would use an explicit stack or raise the recursion limit."
Common Questions
- What is the difference between passing information up and passing it down?
Information goes up in a return value. A parent learns about its subtrees from what the child calls return, so the child calls run first (postorder). Information goes down in an argument. A child learns about the path above it from what its parent passes, so the parent decides first (preorder). Maximum Depth of Binary Tree (LC 104) goes up. Count Good Nodes in Binary Tree (LC 1448) goes down.
- Why does Minimum Depth of Binary Tree (LC 111) fail with
min? An empty child returns 0, and 0 is smaller than any real depth, so
minpicks it. A node with one child is then treated as a leaf. In[2, null, 3, null, 4, null, 5, null, 6]the code returns 1 and not 5. The fix is to use the depth of the child that exists when the other child is missing.- 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 would you avoid the recursion limit on a very deep tree?
Walk the tree level by level with a queue and count the levels, which needs no recursion. Or use an explicit stack that holds
(node, depth)pairs and keep the largest depth. Raisingsys.setrecursionlimitalso works for a depth near 10,000, but each call still uses stack memory.- Balanced Binary Tree (LC 110) needs the height and the balance. How do you get both in
O(N)? Return one value. The call returns the height of the subtree, or -1 when the subtree is not balanced. If a child returns -1, the parent returns -1 at once. Otherwise it compares the two heights and returns
1 + max(left, right). Each node is visited once.
SWE Reasoning
Spot it
- The answer for a node follows from the answers of its left and right subtrees: height, depth, size, balance, lowest common ancestor.
- Moving the same subtree to another place in the tree does not change its answer.
- The wording asks for one number or one yes/no for the whole tree, built from smaller trees.
- You can state in one sentence what
solve(node)returns for the subtree atnode. - Nothing above a node changes what the node should report. If something does, use Top-Down DFS instead.
The invariant, step by step
- Define in one sentence what
solve(node)returns: the finished answer for the subtree atnode. - The base case returns the answer for an empty subtree. It is true by definition, and the value must fit the combine step.
- For a real node, the two child calls run first. By the sentence in step 1, they return the finished answers for the left and right subtrees.
- The combine step builds the answer for this node from those two answers and from
nodeitself. It does not look any deeper. - So the sentence is true for this call, and it is true for every call. The call on the root returns the answer for the whole tree.
Traps
- A base case that does not fit the combine. With
min, an empty child returns 0 and wins. Minimum Depth of Binary Tree (LC 111) needs a check for a missing child. - Two walks for two facts. Calling a separate
heightat every node repeats work. Return both facts from one call, for example -1 for an unbalanced subtree. - A deep chain. A tree with 10,000 nodes in a chain can pass Python's default limit of about 1000 nested calls.
- Returning a node instead of a value. Lowest Common Ancestor of a Binary Tree (LC 236) returns the node found, so a call on
porqmust return that node itself. - Using this card when the answer depends on the ancestors. Then the information must go down as an argument, not up as a return value.