Algorithms for traversing unordered tree

Question

I have been doing some programming 'exercises'. I'm trying to come up with the most efficient algorithm for tree traversal.

Consider the following function signature:

CNode * CNode::find(int number) const

where CNode structure is not organized as a binary search tree (otherwise obviously a faster algorithm would have been used - not involving the entire tree traversal), so all the nodes have to be inspected.

I have implemented 3 algorithms so far:

Stack-based search

CNode * CNode::findStackBased(int number)
{
  Node *tmp = this;
  stack<CNode*> onStack;
  while (tmp != NULL || !onStack.empty())
  {
    if (tmp == NULL)
    {
      tmp = onStack.top();
      onStack.pop();
    }

    if (tmp->number == number)
    {
      return tmp;
    }

    if (tmp->right)
    {
      onStack.push(tmp->right);
    }

    tmp = tmp->left;
  }

  return NULL;
}

Recursive search

CNode * CNode::findRecursion(int number)
{
  if (this->number == number)
  {
    return this;
  }

  Node * result = NULL;
  if (this->left != NULL && (result = left->findRecursion(data)))
  {
    return result;
  }

  if (this->right != NULL)
  {
    return this->right->findRecursion(data);
  }

  return NULL;
}

Walking along the edge

CNode * CNode::findWalkAlongTheEdge(int number)
{
  Node *tmp = this;
  while (tmp != NULL)
  {
    if (tmp->number == number)
    {
      return tmp;
    }

    if (tmp->left != NULL)
    {
      tmp = tmp->left;
      continue;
    }
    else if (tmp->right != NULL)
    {
        tmp = tmp->right;
        continue;
    }
    else
    {
      while (1)
      {
        if (tmp->parent->left == tmp)
        {
          if (tmp->parent->right != NULL)
          {
            tmp = tmp->parent->right;
            break;
          }
        }
        else
        {
          if (tmp->parent == this)
          {
            return NULL;
          }

          tmp = tmp->parent;
        }
      } 
    }
  }
  return NULL;
}

Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).

My question is:

Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?

Answer 1

Do you see any way to optimize it further

I don't see why you have (i.e. don't think you should have) while (tmp != NULL) at the top:

• On entry you know that this != NULL
• You verify that the result won't be NULL before you execute the statement before each continue or break

Removing that would make it slightly faster.

---

Also I don't understand ...

    if (tmp->parent->left == tmp)
    {
      if (tmp->parent->right != NULL)
      {
        tmp = tmp->parent->right;
        break;
      }
    }

... because if (tmp->parent->left == tmp) and (tmp->parent->right == NULL) then you do nothing and therefore stay inside while(1) forever. So perhaps either your code is wrong, or one of those if conditions is unecessary.

---

Apart from the two items above, the existing code looks simple? Multi-threading, using a more-optimizing compiler, or trying to write in assembly are possibilities but not clever. Good optimizations sometimes come from changing the data layout.

For example, one faster algorithm might be to change the way in which the tree is contained in memory: use a custom allocator or similar, to ensure that nodes are physically contained in a contiguous array or vector.

Walking the whole tree would then mean, simply, iterating through the contiguous array: which is pretty quick.

If you do that, it would be easier to change your left, right, and parent pointers to indexes (into the array): because then you wouldn't need to change them if you reallocate (move) the array.

Alternatively keep the nodes in random heap-allocated memory but store the numbers themselves in a contiguous array. Instead of a number member, nodes would have an index member which says which slot in the array contains their number. Making the numbers contiguous (without extraneous tree-node pointers) might be the fastest way to iterate them.

Answer 2

You can simplify all those algorithms a lot by just moving the test for NULL to a single location near the top. Then treating left and write identically (even when NULL).

CNode * CNode::findStackBased(int number)
{
  stack<CNode*> onStack;
  onStack.push(this);

  while(!onStack.empty())
  {
    CNode tmp = onStack.top();
    onStack.pop();

    if (!tmp) {
        continue;
    }

    if (tmp->number == number) {
        return tmp;
    }

    onStack.push(tmp->right);
    onStack.push(tmp->left);
  }

  return NULL;
}

Recursion

CNode* CNode::findRecursion(int number) {
  return findRecusion(this, number);
}
CNode* CNode::findRecursion(CNode node, int number) {

  if ((node == NULL) || (node->number == number) {
      return node;
  }

  return findRecursion(node->left);   // Only do the right side if left
      || findRecursion(node->right);  // returns NULL
}

Walking along the edge just seems to be doing depth first left to right traversal. Its just messy and convoluted. It also requires the concept of a parent pointer.

Each of the above have have some advantages/drawbacks, but performance wise 'walking along the edge is the winner so far(out of the 3 given above).

Really. Please name them.
How are you measuring that? Not convinced that it is actually significantly faster because of all the extra comparisons you are doing. But for certain types of trees it could be faster as you don't need to maintain a stack object.

What you are doing is trading space for time (a common optimization). You are adding a parent pointer into each node to help you do the traversal more quickly. The other two techniques require you to build and maintain a stack (the state of the search (one explicitly and one implicitly in the call stack)) while the walk the edge has the information you need built into the graph.

My question is:

Do you see any way to optimize it further (recursive implementation already benefits from the tail recursion optimization, at least gcc seems to optimize it this way)?

I would be surprised if most compilers don't turn the recursion into a loop. Its an easy optimization. I would worry less about optimization and more about readability. Its usually much more important. The compilers are darn good at making the code fast.