Binary Search With Sorted Array In Ruby

Here’s a quick post to understand the ways a binary tree can be traversed. In a binary tree, each node can have at most two children.

Pre-order Traversal

Log the root first then move (traverse) left. Finally traverse right.

In-order Traversal

Move left first until the node you hit has no children. Log that node, then log the root. Then move on to the right subtree. Typically, for binary search tree, we can retrieve all the data in sorted order using in-order traversal.

Post-order Traversal

Post-order traversal is to traverse the left subtree first. Then traverse the right subtree. Finally, visit the root. When you delete nodes in a tree, deletion process will be in post-order. That is to say, when you delete a node, you will delete its left child and its right child before you delete the node itself.

Here is an implementation of an iterative search through a tree (beginning as a sorted array) I wrote in Ruby:

And because why not, I also wrote a fun poem to help remember the differences between these three three traversal methods. Also the poem itself goes “through time”: eg. “pre-order,” “in-order,” “post-order.” CS students, you’re welcome.

Preorder you log first the root
Then log left, then right to boot
In-order left til nodes are done
Log that, then root, then right for fun
Post-order still log left to start
Log right, then roots are the last part