Binary tree inorder traversal without stack or recursion

Question

I was looking for ways to traverse a binary tree and came across things like Morris Traversal. Except I don't like the idea of modyfying my tree, nor use stack or recursion. Not finding other solution, I wrote my own algorithm. Basically it's depth-first search, but every node has counter of type integer indicating how many times the method traversed this node. Given every node has a parent and two children, this counter takes values from 0 to 2. Therefore the method executes 3 times for every node. Here's the code:

Node root;
public void Traverse() {
 Node node = root;
 while(node != null) {
 node = Get(node);
 }
}
Node Get(Node node) {
 Node child;
 if(node.Counter == 0) {
 child = node.Left;
 }
 else if(node.Counter == 1) {
 child = node.Right;
 System.Console.WriteLine(node);//display node
 }
 else {
 node.Counter = 0;//reset counter
 if(node.Parent != null) {
 node.Parent.Counter++;
 return node.Parent;
 }
 else {
 return null;
 }
 }
 if(child == null) {
 node.Counter++;
 return node;
 }
 return child;
}

My question: in what terms if any, this code is better than Morris traversal or using stack?

• t3chb0t: Does this have any purpose or is it just for fun?
• Suzuya: Do you ask if tree traversal has any purpose? Then yes.
• t3chb0t: Not in general ;-) I'm pretty sure there are some good use cases - I'm rahter asking what you need this for? What is your exact use case?
• Suzuya: As for this exact code, It's rather prototype. I will be using modified version of this, where every node can have multiple nodes. It's for my navigation implementation in my program I'm writing for exercise, if that interests you d
• Pieter Witvoet: Do you have a specific reason for not wanting to use recursion or a stack, other than just not liking it?

Answer 1

Comparison

I don't think this approach offers any benefits compared to Morris traversal, a stack-based or a recursive approach:

• Both this and Morris are modifying the given tree, which I consider to be a negative thing. You're not rearranging nodes like Morris does, but those counter fields still prevent simultaneous traversals. A recursive or stack-based approach does not have that limitation.
• Adding an additional field to your Node class is 'intrusive', and it increases memory use even when you never traverse a tree.
• Unlike the other approaches, yours requires nodes to have a reference to their parent.
• In all the tests I've done (using trees of 100 - 100K nodes) this was consistently slower than Morris, which itself was slower than a recursive or stack-based approach.
• In terms of how easy the code is to understand, I'd say it's similar to Morris, but both are more complicated than a recursive and stack-based approach.

I don't know why you don't like the idea of using recursion. It's actually a very natural approach when working with tree-like structures. It's easy to implement, fast, and doesn't modify the tree or require structural changes.

public void Traverse(Node node, Action<Node> visit)
{
 visit(node);
 if (node.Left != null)
 Traverse(node.Left, visit);
 if (node.Right != null)
 Traverse(node.Right, visit);
}

With recursion there's always a risk of stack overflow, but that should only be a concern when working with highly imbalanced trees.

---

Improved approach

Your approach can be modified so it no longer needs those counter fields. You've got the following states:

• node.Counter == 0: Move to the left child.
• node.Counter == 1: Move to the right child.
• node.Counter == 2: Move back to the parent.

But you can also distinguish between these states if you only keep track of the previously visited node:

• previous == current.Parent: Move to the left child.
• previous == current.Left: Move to the right child.
• previous == current.Right: Move back to the parent.

In terms of performance it's somewhere in-between recursive and Morris. It can also be generalized for nodes with a variable number of children. Still, it remains a relatively complicated approach.

---

Other notes

• The root node should be passed to Traverse as an argument, not via a 'global' variable.
• Get is a very undescriptive name. GetNextNode sounds better, except that it sometimes returns the same node (in a different state), so that name is slightly misleading. Maybe ContinueTraversal?
• Get is only useful within the context of Traverse, so it can be made a local function.
• Those counter values indicate specific states, so I'd use an enum instead of 'magic numbers'. Alternately, you could rename it to something like visitedChildNodeCount.
• Hardcoding System.Console.WriteLine(node) isn't very flexible. Consider passing in the action to be performed as an Action<Node> argument.
• Instead of writing if (condition) { ... } else { return null; }, I'd invert that to if (!condition) return null; ... to reduce nesting.

• t3chb0t: I don't know why you don't like the idea of using recursion. - it's always a pain to debug this things ;-]
• Pieter Witvoet: Fair point. Still, the OP is already using a recursive data-structure, and when in Rome... ;)