Non Recursive Binary Tree Traversal

In my previous post I was talking about drawbacks of recursive approach when traversing tree structures.

In comments on that post, Daemin and w-g mentioned then tail-recursion can be used to avoid function call overhead. Tail-recursion really helps if:
a) language of use supports it
b) your algorithm makes it possible to make a recursive call the last operation in the function

Since, tail-recursion approach is still a recursive one and there is no guarantee that the language of use will support it or the algorithm will allow it - best way not to go into trouble is to make no recursive calls at all.

Here, I'll present non-recursive binary tree traversal. Binary tree is not balanced. To make non-recursive approach possible - tree node was extended with special meta information. It includes reference to the node's parent and a special flag. Flag indicates if node was previously visited during traversal process.

Binary tree node definition in code

class TreeNode { public int Value; public TreeNode Left; public TreeNode Right; public TreeNode Parent; public byte Visited; public TreeNode(int value) { Value = value; } }

Next comes recursive iterator. This method demonstrates recursive approach. It is self-explanatory and very easy to implement. All job is done via recursive call to RecursiveIterator method.

private void RecursiveIterator(TreeNode node) { Console.Write(node.Value + " "); if (node.Left != null) RecursiveIterator(node.Left); if (node.Right != null) RecursiveIterator(node.Right); }

Non-recursive approach on the other hand uses iteration and additional variables to do tree traversal.

private void NonRecursive() { TreeNode currNode = root; while (true) { if (currNode == null) break; if (currNode.Left != null && currNode.Left.Visited != 1) currNode = currNode.Left; else if (currNode.Right != null && currNode.Right.Visited != 1) currNode = currNode.Right; else if (currNode.Visited == 0) { Console.Write(currNode.Value + " "); currNode.Visited = 1; } else currNode = currNode.Parent; } }

Iterative approach is more complicated then recursive, it uses additional data (Parent reference and Visited flag).

So, generally, when you know that your tree structures won't be very deep recursive approach will do. And in the case, when tree depth is quite big, it is better to consider iterative approach.

Why Avoid Recursion For Tree Structures

The subject may seem little bit contradictory. Recursive approach is very convenient when doing search or traversals in a tree structure (e.g. binary tree).

Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large. High memory consumption is due to large function call number (recursion means that function calls itself multiple times).



Every function call results in thread's stack memory consumption. Default stack size is 1 Mb. So, with high recursion depth there is a risk to run out of memory.

Next time I'll present recursive and non-recursive approaches to binary tree traversals.

Google Reader Increase Productivity

Nearly a month ago I've stopped using Internet Explorer 7 as my primart RSS reader. The reasons were:
- IE7 is not quite stable, after 4-5 days of uptime it hangs or crashes
- Feed items are bound to one computer
- It consumes CPU when feeds updating.

So, I've exported my IE7 feeds into an OPML file and imported them into Google Reader.
Now my feeds are all in one place, which is good, their update doesn't take my CPU cycles.

P.S. Lifehacker has some tips how to increase your productivity with Google Reader.

Most amazing tutorial I've ever read

Recently, I've stumbled upon this cool Ruby tutorial. It is called Poignant Guide to Ruby. It is so well written, I wish other programming languages had such tutorials. Even if you're not engaged in Ruby development this book can be a great reading.

Totally recommended! :)