DSA & Algorithms
Part 10 of 21 · DSA Interview PatternsBinary Trees — DFS (Preorder, Inorder, Postorder; Recursion & Stack)
Tree DFS orders with recursion and explicit stack; path and subtree aggregates.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The answer is a path, a subtree, or a traversal order
Prefer
Depth-first, one visit per node
Recursion is the call stack. An explicit stack is the same walk when the tree may be skewed.
- Preorder when the parent is needed before the children.
- Inorder of a binary tree is not sorted unless it is a BST.
- Postorder when both children must finish first.
Alternative
Level order for a root-to-leaf question
BFS answers layers. It is the wrong default for subtree aggregates.
- Returning as soon as one side succeeds when both sides matter.
- Diameter that forgets paths that do not touch the root.
- A recursive walk on a skewed tree with no iterative backup.
Visit, then combine
The order is the interview. The combination step is the actual problem.
- 1
Choose the order
Before children, between them, or after them. - 2
Recurse left and right
Or push the left spine onto an explicit stack. - 3
Combine
Depth, path sum, or a best that lives across calls.
Overview
Tree DFS orders with recursion and explicit stack; path and subtree aggregates.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use DFS for root-to-leaf paths, subtree aggregates, and traversal orders (pre/in/post).
Recognition cues
- max depth / diameter / path sum
- serialize / construct from traversals
- lowest common ancestor (binary tree)
- validate structure via recursion
Mental model
Flow
- 1
1. Stand at the node
- next2. Preorder visits before children
- 2
2. Preorder visits before children
- next3. Inorder visits between children
- 3
3. Inorder visits between children
- next4. Postorder visits after children
- 4
4. Postorder visits after children
- next5. Combine both subtree answers
- 5
5. Combine both subtree answers
Lesson map
Binary Trees — DFS (Preorder, Inorder, Postorder; Recursion & Stack)
Tree DFS orders with recursion and explicit stack; path and subtree aggregates.
Architecture. 1. Stand at the node Ready. 2. Preorder visits before children Ready. 3. Inorder visits between children Ready. 4. Postorder visits after children Ready. 5. Combine both subtree answers Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Root["1. Stand at the node Ready"] Pre["2. Preorder visits before children Ready"] Ino["3. Inorder visits between children Ready"] Post["4. Postorder visits after children Ready"] Comb["5. Combine both subtree answers Ready"] Root -->|continues| Pre Pre -->|continues| Ino Ino -->|continues| Post Post -->|continues| Comb
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Visit each node once: O(n) time.
- Space O(h) recursion/stack (h = height; worst O(n)).
Common pitfalls & interview traps
LeetCode drill (real problems)
- Maximum Depth of Binary Tree
- Binary Tree Inorder Traversal
- Path Sum
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Maximum Path Sum
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Pre vs in vs post?
Answer
Visit before children / between / after - pick by dependency.
Diameter definition?
Answer
Longest path in edges or nodes - clarify; usually edges.
LCA binary tree?
Answer
If root is null, p, or q return root; recurse left and right; if both sides are non-null root is the LCA, else return the non-null side (assumes p and q are in the tree).
Iterative inorder?
Answer
Explicit stack pushing left spine then visit and go right.
Path sum variants?
Answer
Root-to-leaf vs any-to-any (global best) need different state.
Build from traversals?
Answer
Preorder gives root; inorder splits left/right ranges.