A coder post : Link inversion traversal to scan tree in constant space

This is a coder's post and discusses a binary tree traversal technique.

Binary tree is a popular data structure and there are a couple of popular tree traversal techniques. One based on recursion. This includes pre-order, in-order and post-order traversals. The second by using an auxiliary data structure to travel the tree level by level. A pre-order traversal visits a node first then its left child and then its right child. For the example tree below, we visit in pre-order NY then Chicago then Seattle. If it was post order we would see the nodes/places as we travel the tree in this order Chicago, Seattle, NY.

A recursive pre-order traversal code is shown below. i.e we visit a node first then, its left and right children in that order.

The second technique uses a stack as an auxiliary data structure to hold the next nodes to visit. This algorithm pops a node of the stack. Visits the node and pushes its children onto the stack; right child first. To start off push the root of tree on to the stack. For the example tree, we push NY onto the stack. Then, until the stack is empty we pop a node i.e NY here off the stack. Visit NY and then push Seattle and Chicago onto the stack. And repeat. You get the idea.

Recursion has memory, performance overhead for recursive function calls. The auxiliary data structure also has memory overhead. Link inversion traversal goes through the tree as if the links form a solid wall. i.e Imagine walking through your home with one hand always touch the wall. You would have followed the wall(s) one after the other. Similarly link inversion starts from the root walks through the links as if they are walls. An example shown below starts at New York and ends at New York. The exclamation shows the visits. Each node is visited thrice. One each for the pre, post and in-order concepts. (Refer the code below).

Link inversion traversal, uses the tree pointers themselves to store backtracking  information. i.e while going down the tree the links are reversed to aid back track instead of an additional data structure. The links will be restored on the way back through the tree thus leaving the tree as it was. Link inversion traversal needs a couple of extra node references. Also, a bit field on each node to signal the direction we went after first looking at the node. So link inversion generally is referred to as scanning the tree in constant space.  A link inversion code snippet is shown below. The full code for the post is available at the end.

Profiling performance: Link inversion traversal is definitely faster than a pre-order traversal.

Input: A balanced binary search tree of 300+ city names. The link inversion code shows up faster on Netbeans profiler. Notice the recursive time and link inversion time in the screen shot below.

Source code for Link inversion traversal is available at the link below:
https://drive.google.com/folderview?id=0BxhHg0qy5gi4dTlWUC1KU0RUUUU&usp=sharing

References:
1) Data structures and their algorithms by Harry R. Lewis & Larry Denenberg.