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?
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&lt;Node&gt; 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&lt;Node&gt; argument.
Instead of writing if (condition) { ... } else { return null; }, I'd invert that to if (!condition) return null; ... to reduce nesting.