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.
This code is written in JavaScript, but it’s very simple and should translate easily into other languages. Our dfs function takes the root node of the tree as an argument, uses an array called visited to hold the values of visited nodes, traverses the tree with a recursive helper function, and then returns the visited array at the end. There are three different paths the helper function could take, but it’s really just a re-ordering of 3 lines of code!
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!
