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

Question

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.

Section 6.5 of the classic book "The C programming Language" (1988) has an excellent description of binary trees. — user50619
– user50619, Commented Oct 16, 2018 at 10:46
In my experience, the only reasonable way is to maintain your own stack, analogous to the call stack that would have been kept automatically for you if you used recursion. — Steve Summit
– Steve Summit, Commented Oct 16, 2018 at 11:34

Rick de Gier · Accepted Answer · 2018-10-16 10:35:59Z

3

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.

answered Oct 16, 2018 at 10:35

Rick de Gier

622 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

JeremyP Over a year ago

Or you can use a stack if you don't want to alter the data structures.

lrleon · Accepted Answer · 2018-10-17 12:29:04Z

1

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.

answered Oct 17, 2018 at 12:29

lrleon

2,6883 gold badges28 silver badges43 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related