Lesson 102
Tree DFS
Depth-First Traversal
1:00How depth-first search traverses a tree in three distinct orders — pre-, in-, and post-order — using recursion or an explicit stack.
By the end, you can
- Explain what makes DFS "depth-first" and how it differs from BFS.
- State the visit rule for each of the three DFS orders and identify which rule a given traversal sequence was produced by.
- Trace pre-order, in-order, and post-order on any binary tree by hand, node by node.
- Explain why in-order traversal of a BST yields a sorted sequence.
- Choose the appropriate traversal order for a given task (cloning, deletion, sorted output, bottom-up computation).
- Implement iterative DFS with an explicit stack, applying the right-then-left push order to match recursive pre-order.
- State the time and space complexity of DFS and explain why worst-case space is O(n) on a skewed tree.
Up next in Searching & Sorting
