Data Structures & Algorithms in Ruby: Depth-First Search (Pre-order) for Binary Trees

In continuing with our current topic of binary tree traversals in Ruby, we are going to introduce depth-first search this week. If you recall from the last article on breadth-first search, a traversal through a binary tree should be accomplished by visiting each node on the tree only once. That part of the tree traversal should remain a constant. But since trees are non-linear data structures, what is the best way to return all the nodes on the tree in an efficient manner? That is going to depend on what you want the return order to look like. In the example for breadth-first search, the result is returned beginning with the root node, then the two children of the root node, then the two children of the root node’s left child, etc. There are three main types of Depth-First Search: Pre-order, Post-order, and In-order. Today we are going to focus on pre-order.

A Pre-order depth-first search returns the values of the nodes in a binary tree beginning with the root node, and then down one whole side of the tree before going to the other side of the tree and doing the same. This makes it possible to reconstruct the binary tree from just a “flat” list of values. The return of a pre-order depth-first search could look like this: [root, left child of root, left child of left child of root, right child of left…