CODEWITHSUNDEEP
cstructbinary-tree
Jackie
Jackie

Reputation: 372

How can I traverse a binary tree using a while loop?

I was just wondering how I can traverse a binary tree using a while loop (not done recursively).

I have my tree:

typedef struct Node *BSTree;
typedef struct Node {
   int  key;
   BSTree left, right;
} Node;

I just want to know how I can access every single node in a while loop. Could someone show me that? I can't wrap my head around it.

Upvotes: 1

Views: 6353

Answers (2)

lrleon
lrleon

Reputation: 2648

You can use a stack for storing the parents that you need to visit when returning from an already visited branch. A way in pseudo-C++ for a preorder traversal:

void (Node * root)
{
  if (root == NULL) 
    return;

  Stack<Node *> stack;
  stack.push(root); 

  Node * p;
  while (not stack.is_empty())
    {
      p = stack.pop();

      // here you visit p 

      if (p->right != NULL)
        stack.push(p->left);

      if (p->left != NULL)
        stack.push(p->right);
    }
}

Note that the left and right branches are pushed in an inverted way, so the first to pop is the left one.

Upvotes: 1

Rick de Gier
Rick de Gier

Reputation: 62

You need to have a reference to the parent Node.

if root != null store root in current. If current has a left child you set current to left child. If there is no left child and there is a right child store right child in current. If there is no left and right child store parent of current node in in current.

if you take this you will end up in endless loop but if you store the one before the current and compare the relation between the current node and the last node you can traverse the whole tree.

This is not the full answer but it will help.

Upvotes: 3

Related Questions