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; } 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.