Today’s goal is to build a Depth First Preorder Traversal. This algorithm is where a tree is searched by checking the current node, searching the children to the left and finally searching the children to the right. Following this pattern will search a tree from the outer edges left to right. Day 9’s code will be our starting point and we should only need to build our tree and write the traversal method(s). The algorithm we will follow has the following steps.
Get the root node
Record the node value
If a lesser node exists goto step 2 with lesser as the target
If a greater node exists goto step 2 with greater as the target
We should start with an RSpec test to construct and verify our tree structure. A tree that should look like the diagram below.
This test should and does pass without adding any additional code. We now can be confident of the tree structure we will be working with. Now we should add tests to specify what results our traversal should return.
All of these tests will fail and we must write a recursive method to meet these needs. Fortunately Binary Trees lend themselves very well to recursive solutions. The plan is to pass an array into the methods to record the path taken by the algorithm.
With our tests passing now we have successfully written pre-order traversal using recursion. Let’s look into how we would achieve the same results using iteration. It can be very difficult to envision using iteration to solve a problem that so obviously lends itself to recursion.
Unfortunately, because recursion is so intrinsic to the definition of a preorder traversal, you may have trouble finding an entirely different iterative
algorithm to use in place of the recursive algorithm. In such a case, the best course of action is to understand what is happening in the recursion and try to
emulate the process iteratively.
Programming Interviews Exposed
This was a very helpful piece of advice and it was much easier to solve the problem while keeping it in mind. Essentially we need to use a stack and loop through nodes emulating recursion. An array will satisfy the need for a stack. The tests and code are below.
On Algorithmathon Day 11 we will be looking into finding the Lowest Common Ancestor of two nodes in a tree.