If this blog helped you in any way, please donate a dollar here

Monday, August 8, 2011

Iterative Inorder Traversal of Binary Search Tree

A student from my undergrad college asked an innocent question to me on a facebook group to write an iterative implementation for In-Order Traversal of a Binary Search Tree. Of course I obliged and wrote up a code. However, I had never dug deeper into the properties of such traversals before and my observation was quite unexpected.

I was asked a question in the M.Tech. programme interview at NIT Durgapur about the significance of In-Order traversals of BSTs. I wasn't aware of any! So I gave a prompt reply, that it prints the elements in a sorted order. I was sure I was correct but the expression on their faces led me believing I was surely wrong! Oh well, I never did study theory before, so I guess my anguish was justified.

So, for my fellow junior, here's the code I promised:




/*
 * Iterative Inorder Traversal
 * by Rahul Ghose 
 * 09.08.2011 02:23:42
 */
 
#include 
#include 
 
using namespace std;
 
struct mytree {
        int data;
        struct mytree *left;
        struct mytree *right;
};
 
struct mytree* newNode(int data) { 
        struct mytree* node = new struct mytree;
        node->data = data; 
        node->left = NULL; 
        node->right = NULL;
        return node;
} 
 
struct mytree* insert(struct mytree* node, int data) { 
        if (node == NULL) { 
                return(newNode(data)); 
        }
        
        if (data <= node->data) node->left = insert(node->left, data); 
        else node->right = insert(node->right, data);
        return(node); 
}
 
int main() {
        struct mytree *tree = NULL;
        stack<pair<struct mytree*,bool> > s;
 
        tree = insert(tree,20);
        tree = insert(tree, 5);
        tree = insert(tree,29);
        tree = insert(tree,15);
        tree = insert(tree, 4);
        tree = insert(tree,21);
        tree = insert(tree,32);
 
        s.push(make_pair(tree,false));
 
        while(!s.empty()) {
                pair<struct mytree*,bool> pp = s.top();
                struct mytree *t = pp.first;
                if(pp.second) { // marked
                        printf( "%d ", t->data );
                        s.pop();
                        if( t->right ) {
                                s.push( make_pair(t->right,false));
                        }
                        continue;
                }
                if(t->left) {
                        s.pop();
                        s.push(make_pair(t,true));      // mark for deletion
                        s.push(make_pair(t->left,false));
                }
                else {
                        printf( "%d ", t->data );
                        s.pop();
                        if( t->right ) {
                                s.push( make_pair(t->right,false));
                        }
                }
        }
 
 
        return 0;
}


Also on ideone : http://ideone.com/t118h

2 comments:

  1. Hello,

    I am Thomas John, representing the website Ubuntu Manual. As the name suggests UM is a site that delivers content related to Ubuntu, its derivatives and related software. We are looking to expand our website and are seeking talented writers familiar with Ubuntu or Linux or similar open source software to include in our community of writers.

    We had come across your article on the web and was wondering whether you would be interested in writing for us. We can provide sufficient compensation for your writings and would love to have you as one of our writers.

    I will provide you with the rest of the details if you are interested.

    Cheers,
    --
    Thomas John,
    Ubuntu Manual

    ReplyDelete
  2. Hi,

    Mr. Thomas John and thanks for you gracious comments. I was unable to e-mail you since you have not left your address here. Please do contact me at: hansum [dot] rahul [at] gmail [dot] com

    Thanks :)

    ReplyDelete