Data Structures & Algorithms

Binary Tree Traversals
Unlike linear data structures (arrays, linked lists, queues, stacks) which have only one logical way to traverse them, trees can be traversed in different ways. There are 3 common techniques for traversing trees: preorder, inorder, & postorder. 

Traversal Techniques

Visualizations & Memory Tricks

Using a combination of python-igraph and imageio, I created 3 gifs to show the most common traversal techniques. Since memorizing the pattern of each technique can be difficult, I included some tricks to help us not forget.

Think of each technique as a different button on your remote:

Preorder
Root – Left – Right

Inorder
Left – Root – Right

Postorder
Left – Right – Root

Preorder Traversal

Method #1:

Memory trick for Preorder Traversal: You are watching a sports game but you missed the pre-game highlights,  so you rewind.  You are probably one of those people who likes to start things from the top/root. Picture a rewind button:
 

Imagine each node has a rewind button pointing left and you can only access nodes where you have clear access to the left arrows.

Inorder Traversal

Method #2:

Memory trick for Inorder Traversal: Sometimes, “in order” to watch something, you have to download it first. Picture a download button:
 

Imagine each node has a download button pointing downwards and you can only access nodes where you have clear access to the down arrows.

postorder Traversal

Method #3:

Memory trick for Postorder Traversal: You downloaded a sports event, but all you want is the post-game highlights,  so you fast forward.  Picture a fast forward button:
 

Imagine each node has a fast forward button pointing right and you can only access nodes where you have clear access to the right arrows.