Data Structures & Algorithms in Ruby: Depth-First Search (Post-order) for Binary Trees
Last week we introduced the concept of Depth-First Search for Binary Tree traversals. Of the three main types of Depth-First Search (DFS) algorithms, we began with a pre-order search, which begins at the root node of the binary tree and returns each node visited on the way down the left side of the tree, then down the right side of the tree. Like our discussion of Breadth-First Search, the root node is the first value returned in a pre-order DFS. In a Depth-First Search Post-Order algorithm, the first value in our returned list would be the deepest node on the left side of the tree. To keep things simple and consistent, we will use the same Binary Search Tree as an example:
For comparison purposes, a Breadth-First Search of this Binary Search Tree would return the values:
50, 40, 60, 10, 55, 100, 2, 20, 95, 30, 64, 26, 33
A Depth-First Search Pre-Order algorithm would return the values in this order:
50, 40, 10, 2, 20, 30, 26, 33, 60, 55, 100, 95, 64
Notice how in the DFS pre-order the return values follow the nodes starting with the root then all the way down the left side of the tree first, then add any right node siblings before traversing the right side of the tree.
