# Binary tree inorder traversal without stack or recursion

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?

• Does this have any purpose or is it just for fun? – t3chb0t Oct 28 '18 at 7:16
• Do you ask if tree traversal has any purpose? Then yes. – Suzuya Oct 28 '18 at 10:03
• 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? – t3chb0t Oct 28 '18 at 10:51
• 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; – Suzuya Oct 28 '18 at 17:32
• Do you have a specific reason for not wanting to use recursion or a stack, other than just not liking it? – Pieter Witvoet Oct 29 '18 at 8:57

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.
• I don't know why you don't like the idea of using recursion. - it's always a pain to debug this things ;-] – t3chb0t Nov 1 '18 at 10:06
• Fair point. Still, the OP is already using a recursive data-structure, and when in Rome... ;) – Pieter Witvoet Nov 1 '18 at 10:18