For no reason in particular I decided to revisit tree traversal as a kind of programming kata. There are two main kinds of tree traversal:
- Depth first – This is where you go all the way down a tree’s branches first before bubbling up to do work. With a tree like below, you’d hit
cbefore doing any work since it’s the deepest part of the tree (assuming you iterated left first then right)
a / \ b e / \ c d
- Breadth first – This is where you hit all the nodes at the level you’re on before going further. So with the same tree, you’d hit a, then b, then e, then c and d.
Being as I actually hate tree traversal, and having to think about it, I decided that whatever I write better be extensible and clean.
Here is a simple DFS … Read more