A non-recursive implementation of an in-order traversal of a binary search tree without a stack

In my spare time, I occasionally was reading a book: “Introduction to algorithms” written by Cordon et al. to refresh and extend my knowledge on this field. Reading a book on algorithms has a side affect on me, that sooner or later I end up playing around with algorithm’s code. This time I wanted to get a non-recursive traversal of a BST without using an auxiliary stack. While a recursive traversal of a BST is really trivial, a non-recursive one is not. At least not in my eyes.
First, this is a simple API which I decided to use for a BST:

template <class T> class btree;
 
template <class T> struct node
{
public:
  friend class btree<T>;
   
private:
  T *data;
  node *left;
  node *right;
};
 

template <class T> class btree
{
public:
  btree (std::function<int(const T&, const T&)> cmp);
  ~btree ();
...
  void foreach2 (std::function<void(T&)> func) const;
...
   
private:
  node<T> *root;
  std::function<int(const T&, const T&)> cmp;
...
};

So, as you can observe, there are two classes: a node and the btree itself. The constructor of a btree takes a compare function to be able to compare its elements while searching, for example. However, this post is actually dedicated to the foreach2 member function, which travels in-order through the whole BST and takes a function as a parameter to do some action with a node’s item.

Next, I try to introduce this algorithm step by step. This way to traverse a tree is not really efficient as it visits most of the nodes almost twice on one side, but on the other side it does not require any additional data structure to keep track how to return to the parent node. All in one, it’s a lot of fun:) Below you see the whole algorithm, and as you will find out, despite the fact that this code is really small, at first glance, it’s really hard to figure out, how it works and why it works at all. So, just scroll over.

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    if (i->left != nullptr) {
      node<T> *r = i->left;
 
      while (r->right != nullptr && r->right != i) {
        r = r->right;
      }
 
      if (r->right == nullptr) {
        r->right = i;
        i = i->left;
        continue;
      } else {
        r->right = nullptr;
      }
    }
 
    func (*i->data);
    i = i->right;
  }
}

So, let’s build it from scratch. Therefore, we consider a few simple cases of a BST. Suppose all node in our BST have no left nodes, so it has a form similar to this one:

//    A
//   / \
//      B
//     / \
//        C
//       / \

To traverse this BST and thus cover this case, the lines of code we come up with should be very simple:

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    ...
    func (*i->data);
    i = i->right;
  }
}

And it’s no wonder, because it’s just the code, which is used to go through the singly linked list. Therefore let’s consider another special case, in which all nodes have no right child.

//       A
//      / \
//     B
//    / \
//   C
//  / \

To be able to traverse this, we should first go to the bottom of the left subtree. Let us therefore add this part of the code:

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    if (i->left != nullptr) {
      ...
      i = i->left;
      continue;
      ...
    }
 
    func (*i->data);
    i = i->right;
  }
}

Once, we have arrived at the bottom we perform an operation on C’s data and bump we are stuck! At this point we should go backwards the tree. However, there is no way to go back and it’s too late already. Nevertheless, from the bottom position we can make an interesting observation: taking an arbitrary tree structure into account, all nodes at which we are going to stuck will have no right child set. Hence, at the beginning while moving down the left subtree, we should find a predecessor of the current node (in the sense of in-order traversal order) and temporarily adjust its right child to this node i.e. while visiting node A, we find its predecessor and it’s B, we set its right child temporarily to A and go one step down in the left subtree to B. For the node B we do absolutely the same thing.
Once we will arrive to the node A for the second time we should revert the temporary change by setting B’s right link to null pointer again, proceed with the data of node A and finally move to the right subtree. Remarkably, this is all what is required to be able to traverse a BST of any arbitrary structure.

Bellow you can find the entire example, in which a randomly build BST containing 50 items is constructed and traversed in-order afterwards, printing its items:

#include <functional>
#include <iostream>
#include <random>
#include <algorithm>

template <class T> class btree;

template <class T> struct node 
{
public:
  friend class btree<T>;
  
private:
  T *data;
  node *left;
  node *right;
};

template <class T> class btree
{
public:
  btree (std::function<int(const T&, const T&)> cmp);
  ~btree ();

  void insert (const T& data);
  void foreach (std::function<void(T&)> func) const;
  void foreach2 (std::function<void(T&)> func) const;
  int length () const;
  void remove (const T& data);
  
private:
  node<T> *root;
  std::function<int(const T&, const T&)> cmp;

  void foreach (node <T>* node, std::function<void(T&)> func) const;
  int length (node<T> *node, int len) const;
};

template <class T>
btree<T>::btree (std::function<int(const T&, const T&)> cmp)
{
  root = nullptr;
  this->cmp = cmp;
}

template <class T>
btree<T>::~btree ()
{
}

template <class T>
int btree<T>::length () const
{
  return length (root, 0);
}

template <class T>
int btree<T>::length (node<T> *node, int len) const
{
  if (node != NULL) {
    int l1, l2;
    l1 = length (node->left, len + 1);
    l2 = length (node->right, len + 1);

    return std::max (l1, l2);
  }
  
  return len;
}

template <class T>
void btree<T>::foreach (std::function<void(T&)> func) const
{
  foreach (root, func);
}

template <class T>
void btree<T>::foreach (node<T> *node, std::function<void(T&)> func) const
{
  if (node != NULL) {
    foreach (node->left, func);
    func (*node->data);
    foreach (node->right, func);
  }
}

template <class T>
void btree<T>::remove (const T& data)
{
  node<T> *i = root;
  node<T> *p = nullptr;
  node<T> *s = nullptr;
  int val;

  while (i != nullptr && (val = cmp (data, *i->data)) != 0) {
    p = i;
    if (val > 0) {
      i = i->right;
    } else {
      i = i->left;
    }
  }

  if (i == nullptr) return;

  if (i->left == nullptr) {
    s = i->right;
  } else if (i->right == nullptr) {
    s = i->left;
  } else {
    node<T> *b = i;
    s = i->right;

    while (s->left != nullptr) {
      b = s;
      s = s->left;
    }

    if (b->left == s) {
      b->left = s->right;
    } else {
      b->right = s->right;
    }

    s->left = i->left;
    s->right = i->right;
  }

  if (p == nullptr) {
    root = s;
  } else if (p->left == i) {
    p->left = s;
  } else {
    p->right = s;
  }
  
  delete i->data;
  delete i;
}

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;

  while (i != nullptr) {
    if (i->left != nullptr) {
      node<T> *r = i->left;

      while (r->right != nullptr && r->right != i) {
        r = r->right;
      }

      if (r->right == nullptr) {
        r->right = i;
        i = i->left;
        continue;
      } else {
        r->right = nullptr;
      }
    }

    func (*i->data);
    i = i->right;
  }
}

template <class T>
void btree<T>::insert (const T& data)
{
  node<T> *n = new node<T>;
  n->data = new T (data);
  n->left = nullptr;
  n->right = nullptr;

  node<T> *i = root;
  node<T> *p = nullptr;

  while (i != nullptr) {
    p = i;
    if (cmp (*i->data, *n->data) >= 0) {
      i = i->left;
    } else {
      i = i->right;
    }
  }

  if (p == nullptr) {
    root = n;
  } else if (cmp (*p->data, *n->data) >= 0) {
      p->left = n;
  } else {
      p->right = n;
  }
}

int main ()
{
  std::random_device rd;
  std::uniform_int_distribution<int> dist (0, 1000);

  std::cout << "testing..." << std::endl;
  btree<int> bt([] (const int &a, const int &b) -> int { return (a - b); });
  int num;
  for (int i = 0; i < 50; i ++) {
    num = dist (rd);
    bt.insert (num);
  }

  bt.foreach ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;

  bt.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  std::cout << "length: " << bt.length () << std::endl;
  
  std::cout << "testing delete..." << std::endl;
  btree<int> bt2([] (const int &a, const int &b) -> int { return (a - b); });
  int vals[] = { 12, 20, 8, 10, 4, 3, 2, 1 };
  for (int i = 0; i < sizeof (vals)/sizeof (vals[0]); i++) {
    bt2.insert (vals[i]);
  }
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  bt2.remove (8);
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  bt2.remove (12);
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
}

It can be compiled with:

all:
	g++ inorder.cpp -o inorder --std=c++11 -O3

Reference: Threaded binary tree

Advertisements

Recursively defined lambda functions in C++11

A neat feature, which was introduced in since C++11 is the ability to define a lambda functions[1] in combination with delegates represented by std::function[2]. The following exemplary code snippet demonstrates how a recursive lambda function can be constructed this way:

#include <functional>
#include <iostream>

int main () {
  std::function<void(int)> count_down;

  count_down = [&count_down] (int num) -> void {
    if (num > 0) {
      std::cout << "i:" << num << std::endl;
      
      count_down (num - 1);
    }
  };

  count_down (6);
}

Using GCC, the above code can be compiled with:

$ g++ testcase.cpp -o testcase --std=c++11

[1] http://en.cppreference.com/w/cpp/language/lambda
[2] http://en.cppreference.com/w/cpp/utility/functional/function