Tree traversal techniques

Lately, I’ve been trying to systematically organize tree traversal techniques in a structural way, and I realized that there were some missing concepts I took for granted for years (e.g. I used to assume that BFS is just a post-order traversal 😅) . Therefore, I’m writing this to help clear the confusion, and hopefully it will help others to have a better understanding of different traversal techniques, too.

  • Pre-order traversal
  • Post-order traversal
  • Level-order traversal (a.k.a Breath First Search)

In-order traversal

In-order traversal is the traversing technique which traverses the tree on the exact relative order: left child -> current node -> right child. It’s also called Depth-First-Search (DFS) since it will have to visit it’s left nodes first before itself.

[4, 2, 5, 1, 6, 3]

Pre-order traversal

Similar to in-order traversal implementation, the only difference is that pre-order traversal has the ordering: current node -> left child -> right child

[1, 2, 4, 5, 3, 6]

Post-order traversal

Similar to the above implementation, the only difference is the traversing order now is: left child -> right child -> root

[4, 5, 2, 6, 3, 1]

Level-order traversal

Unlike the other 3 techniques, level-order is probably the most intuitive and consumable traversal technique since it visits nodes level-by-level. That’s why it’s also called Breath First Search.

[1, 2, 3, 4, 5, 6]

Work hard, stay humble

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store