0
\$\begingroup\$

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?

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.