CODEWITHSUNDEEP
algorithmbinary-search-treetree-traversaliterationinorder
OmarOthman
OmarOthman

Reputation: 1728

How to do in-order traversal of a BST without recursion or stack but using parent pointers?

Is it possible to do an iterative in-order-traversal on a BST whose node has a parent pointer (the parent of the root is null) without using a visited flag or a stack?

I googled and didn't find a reply. The point is, how can I know - at a certain node - that I've just come to it vs I've finished everything underneath it?

Upvotes: 18

Views: 20702

Answers (8)

Vaughn Cato
Vaughn Cato

Reputation: 64308

Here is another way to do it. I think it is essentially equivalent to svick's answer, but avoids the extra variable. This version is implemented in Python:

node=root
if node is not None:
  while node.left is not None:
    node=node.left
  while node is not None:
    output(node)
    if node.right is not None:
      node=node.right
      while node.left is not None:
        node=node.left
    else:
      while node.parent is not None and node.parent.right is node:
        node=node.parent
      node=node.parent

Whatever node you visited last determines the next node that you need to visit. If you've just visited node X, then you need to visit the left-most node to the right of X. If X has no right child, then the next node is the first ancestor where node X didn't come from the right side.

Upvotes: 14

rahul
rahul

Reputation: 1473

Step 1 : write a function which returns the in-order successor

Step 2 : Starting with the leftmost node, find the in-order successor until there is none

    public class TreeNode {
      int data;
      TreeNode left;
      TreeNode right;
      TreeNode parent;
    }

    public class TreeUtility {
      public void inorderNoRecursion(TreeNode root) {
        TreeNode current = leftmostNode(root);
        while(current != null) {
          System.out.println(current.data);
          current = inorderSuccessor(current);
        }
      }

      public TreeNode inorderSuccessor(TreeNode node) {
        if (node.right!=null) {
          return leftmostNode(node.right);
        }

        TreeNode p = node.parent;
        TreeNode c = node;
        while(p!=null && c != p.left) {
          c = p;
          p = p.parent;
        }
        return p;
      }

      private TreeNode leftmostNode(TreeNode node) {
        while (node.left != null) {
          node = node.left;
        }
        return node;
      }
    }

Upvotes: 0

Kanagavelu Sugumar
Kanagavelu Sugumar

Reputation: 19260

My Java solution without introducing any flag on the existing TREE. And no parent pointer as well. This approach will hold nodes up to the height of the tree. Please have a look.

https://github.com/skanagavelu/Algorithams/blob/master/src/tree/InOrderTraversalIterative.java

Upvotes: 0

Raj Srinivasan
Raj Srinivasan

Reputation: 17

public void inorderNoStack() {
    if (root == null) {
        return;
    }

    // use the previous to always track the last visited node
    // helps in deciding if we are going down/up
    Node prev = null;

    Node curr = root;

    while (curr != null) {
        // going down
        if (prev == null || prev.left == curr || prev.right == curr) {
            if (curr.left != null) {
                prev = curr;
                curr = curr.left;
                continue;
            } else {

                visitn(curr);

                if (curr.right != null) {
                    prev = curr;
                    curr = curr.right;
                    continue;
                } else {
                    // swap states
                    prev = curr;
                    curr = prev.parent;
                }
            }
        }

        // going up after left traversal
        if (curr != null && prev == curr.left) {

            visitn(curr);

            if (curr.right != null) {
                prev = curr;
                curr = curr.right;
                continue;
            } else {
                // swap states
                prev = curr;
                curr = prev.parent;
            }
        }

        // going up after right traversal
        if (curr != null && prev == curr.right) {
            // swap states
            prev = curr;
            curr = prev.parent;
        }
    }
}

Upvotes: 0

Sasi
Sasi

Reputation: 1

This is in C++:

void InOrder(Node *r)
{
   if(r==NULL)
         return;

   Node *t=r;

   while(t!=NULL)
       t=t->left;

  while(t!=r)
  {
     if(t==(t->parent->left))
     {
        cout<<t->parent->data;
        t=t->parent->right;
       if(t!=NULL)
      {
       while(t!=NULL)
          t=t->left;
      } 
      if(t==NULL)
          t=t->parent;
     }
     if(t==t->parent->right)
     {
        t=t->parent;
     }
  }
}

Upvotes: -2

svick
svick

Reputation: 244787

You can do that, you just need to remember the last visited node along with the current node. Doing this is not disallowed by the problem statement: both visited flag on each node and a stack are (worst case) O(n), remembering the last node is just O(1).

In C#, the algorithm could look like this:

static void Walk(Node node)
{
    Node lastNode = null;
    while (node != null)
    {
        if (lastNode == node.Parent)
        {
            if (node.Left != null)
            {
                lastNode = node;
                node = node.Left;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Left)
        {
            Output(node);

            if (node.Right != null)
            {
                lastNode = node;
                node = node.Right;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Right)
        {
            lastNode = node;
            node = node.Parent;
        }
    }
}

Upvotes: 20

OmarOthman
OmarOthman

Reputation: 1728

Using svick's correct idea (see his answer), this is the tested code in C++. Note that I didn't test his code or even take a look at it, I just took his idea and implemented my own function.

void in_order_traversal_iterative_with_parent(node* root) {
node* current = root;
node* previous = NULL;

while (current) {
    if (previous == current->parent) { // Traversing down the tree.
        previous = current;
        if (current->left) {
            current = current->left;
        } else {
            cout << ' ' << current->data;
            if (current->right)
                current = current->right;
            else
                current = current->parent;
        }
    } else if (previous == current->left) { // Traversing up the tree from the left.
        previous = current;
        cout << ' ' << current->data;
        if (current->right)
            current = current->right;
        else
            current = current->parent;
    } else if (previous == current->right) { // Traversing up the tree from the right.
        previous = current;
        current = current->parent;
    }
}

cout << endl;
}

Upvotes: 6

oqi
oqi

Reputation: 122

The key is the parent pointers (or the ability to mutate the tree), but you need a constant amount of extra state (e.g., the program counter of the following coroutine).

  1. Set v to the root.
  2. While v has a left child, set v to its left child.
  3. Yield v.
  4. If v is the root, then return.
  5. Set p to v's parent.
  6. If p's right child is v, then set v to p and go to step 4.
  7. Yield p.
  8. If p has a right child, then set v to p's right child and go to step 2.
  9. Set v to p and go to step 4.

Upvotes: -1

Related Questions