Home > Articles, Data Structures & Algorithms > Implementation of algorithms (without recursion) for preorder & level-order traversal of binary trees.

Implementation of algorithms (without recursion) for preorder & level-order traversal of binary trees.

The iterative (non-recursive) function preorderTreeTraverse() can perform preorder traversing of a binary tree with the help of a stack that can hold pointers to nodes of the tree.

Also, the iterative (non-recursive) function layerTreeTraverse() can perform level-order traversing of a binary tree with the help of a queue that can hold pointers to nodes of the tree.

void
preorderTreeTraverse (link h, void visit (link)) {
  STACK<link> s (max);

  s.push (h);

  while (!s.empty ()) {
    visit (h = s.pop ());

    if (h->r != 0) s.push (h->r);
    if (h->l != 0) s.push (h->l);
  }
}

void
layerTreeTraverse (link h, void visit (link)) {
  QUEUE<link> q (max);

  q.put (h);

  while (!q.empty ()) {
    visit (h = q.get ());

    if (h->l != 0) q.put (h->l);
    if (h->r != 0) q.put (h->r);
  }
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: