How to do pre-order and post-order traversal of THREADED binary search tree?

Question

Okay, so in-order traversal of threaded binary tree by using threads goes something like this:

1. Start at leftmost node and print it
2. Follow thread to right and print it
3. Follow link to right go to leftmost node and print it
4. Follow thread to right and print it
5. (repeat)

But how can I make pre- and post-order traversals using threads?

Answer 1

A threaded tree node typically has a flag that tells you whether the right and left pointers in the node are references to children, or threads to the inorder/preorder successor. That's the only way you can tell if the node is a leaf.

The nice thing about a threaded tree is that inorder or reverse inorder traversals can be done quickly without recursion. But a threaded tree doesn't help you with postorder or preorder traversals. If you want to do one of those, you have to use the recursive algorithm, taking the threads into account. For example:

preorder(node)
    print node
    if (node.left is not a thread link)
        preorder(node.left)
    if (node.right is not a thread link)
        preorder(node.right)

postorder(node)
    if (node.left is not a thread link)
        preorder(node.left)
    if (node.right is not a thread link)
        preorder(node.right)
    print node

Answer 2

we can able to do inorder traversal in threaded binary tree as provided above but also we can able to do preorder traversal without using any extra space also . this is c++ code

//code is here

//////////////////////////////////////////
void preorder(node*root)
{
    if (root==NULL)
    {
        cout <<"tree is empty \n";
    }
    else
    {
        while(root!=NULL)
        {
            cout <<root->data;
            if (root->lthread==false)
            {
                root=root->lptr;
            }
            else if (root->rthread==false)
            {
                root=root->rptr;
            }
            else
            {
                while(root!=NULL&&root->rthread==true)
                {
                    root=inorder_succesor(root);
                }
                if (root!=NULL)
                {
                    root=root->rptr;
                }
            }
        }
    }
}
///////////////////////////////////////////////////////

as we know in preorder traversal we first print the node where we are and then go to left subtree and then rightsubtree then here we able to do this

1.print the node at which we are .

2.if this node has left subtree then go to it and print its node and go to step 1

3.is node has no left subtree check is it has right subtree , if yes go to right subtree and go to step 1

4. we reach to this step when we have node having no left subtree and no right subtree then we go to its inorder succesor which has right subtree and go to right subtree and go to step 1 is we get is can not get any inorder successor having right subtree then stop .