DFS CHEAT SHEET
If you, like me, have been mystified by binary trees in your data structures journey, you might enjoy this little cheat sheet I built for myself to try to remember the differences in implementing depth-first searches in pre-, post-, and in-order traversal. Breadth-first search takes a little more set-up, but there’s only one method of traversal there to remember. While studying trees, I noticed that the code for all 3 DFS is super-similar except for tiny changes in the helper function that’s used to move from node to node.
Pre-order starts at the root, then visits the left side, then the right side. Post-order visits the left side, then the right side, then the root last of all. In-order visits the left side, then the root, then the right side.
Obviously there’s a lot of recursion and call-stack stuff going on behind the scenes, but I find it helpful to look at the code like this to analyze how the call stack is being populated and I hope you do too!