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

We have now come of the final of the three main types of Depth-First Search (DFS) for a Binary Search Tree: In-Order traversal. DFS In-Order, as far as I am concerned, is probably the most useful as the return values are delivered as a sorted array from lowest to highest value.

First, a very brief recap of what we covered so far for Binary Search Tree traversals:

· A Binary Search Tree is a data structure wherein each node has at most two child-nodes (hence the term Binary)

· The child node to the left is always smaller than the parent node.

· The child node to the right is always larger than the parent node.

· The two main ways to traverse a Binary Search Tree while only touching each node once are called Breadth-First Search and Depth-First Search

· In Breadth-First Search, the nodes are returned in horizontal order from the top down, such that the first node returned is the root node, followed by the root node’s two child nodes, followed by the root node’s grandchildren nodes, etc.

· Depth-First Search algorithms come in three main varieties: Pre-Order, Post-Order, and In-Order.

· In DFS Pre-Order, the values are returned in the order that they are visited from the root node, then down the left side of the tree, then down the right side of the tree.