Ronzii's Blog

Just your average geek's blog

Morris Traversal

void MorrisTraversal(TreeNode *root)
{
    TreeNode* current = root;
    while(current!=NULL)
    {
        if(current->left==NULL)
        {
            cout<<current->value<<" ";
            current = current->right;
        }
        else
        {
            TreeNode* pre = current->left;
            while(pre->right!=NULL && pre->right!=current)
            {
                pre = pre->right;
            }
            if(pre->right==NULL)
            {
                pre->right = current;
                current = current->left;
            }
            else
            {
                pre->right =NULL;
                cout<<current->value<<" ";
                current = current->right;
            }
        }
    }
}

March 1, 2012 Posted by | C++ | , , , , | Leave a comment

Level Order Traversal in Tree

It’s a pretty popular algorithm based interview question and it helps to have studied graphs because Breadth First Search and a bit of STL makes this program very easy to implement. The example of level order traversal is to print the nodes in the following order : –

struct node
{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node TreeNode;
void printLevelOrderTraversal(TreeNode* &root)
{
    queue<TreeNode*> q;
    TreeNode* current;
    current = root;
    while(current!=NULL)
    {
        printf("%d\n",current->value);
        if(current->left) q.push(current->left);
        if(current->right) q.push(current->right);
        current = q.front();
        q.pop();
    }
}

July 11, 2011 Posted by | C++, Data Structures | , , , , | Leave a comment