Construct Single threaded binary tree–In-order successor connection

“The main advantage of threaded trees is the reduction in traversal time and space.. Tree traversal is really time consuming + stack space consuming. We can reduce that, if we have threaded the tree with the empty nodes at the bottom.”

Introduction

   Before diving into the concept behind this, understand and re-study the following links,

http://analgorithmaday.blogspot.com/2011/03/successor-and-predecessorbst.html

http://analgorithmaday.blogspot.com/2011/06/applications-of-traversals.html

In this article, we will just see how to thread the tree so that, all the leaf nodes get connected to its in-order successor nodes. As its a successor node, we connect the right nodes to the appropriate root.

Concept

The important property of the in-order successor node is that,

• If the node you see has a NULL right node and the node is present as left child for its parent, simply connect the NULL node to the parent.
• If the node you see has a NULL right node but its a right child for its parent, then move to a parent for which our node is not the right!!

This is already discussed clearly in successor and predecessor. But how to do this with recursion and without a parent node part of the tree!!

Little bit tricky!!.. :) But if you understand that, you need to create cycles with the current parent. you will catch the way!!

i.e,

Consider you have a tree like this,

           

Firstly, you need to do recursion so that child gets connected to parent. That is,

7->3, 8->3, 3->1,9->4, 4->1.. etc.

After you get this recursion, connect 7->right to 3 and 8->right also to 3. But when you need to connect 3 to 1, you just check whether traversing 3->right->right gives again the 3.. :)

That is, 

          1

     3

7       8 –> right node connected to 3.

Between 3 and 8 there is a cycle, just detect this cycle and move the 8-th right node to the parent of 3. which is 1. :)

The above is what we need to achieve to get the in-order successor.

Code

Tree* makeThreaded(Tree* root)

{

    if(root == NULL)

        return NULL;

    Tree* leftPrev = makeThreaded(root->left);

    if(leftPrev != NULL) {

        std::cout<<leftPrev->data;

        std::cout<<":"<<root->data<<std::endl;

        Tree* iter = leftPrev;

        while(iter->right != NULL && iter->right != leftPrev)

            iter = iter->right;

        iter->right = root;

    }

    Tree* rightPrev = makeThreaded(root->right);

    if(rightPrev != NULL) {

        std::cout<<rightPrev->data;

        std::cout<<":"<<root->data<<std::endl;

        Tree* iter = rightPrev;

        while(iter->right != NULL && iter->right != rightPrev)

            iter = iter->right;

        iter->right = root;

    }

    return root;

}

Tree* tobj = newTree();

Tree* root = makeThreaded(tobj); // there will be no change in root

• we need to iterate until we find the right!!.. That’s why we need that for loop.
• we don’t use any extra space in this algorithm. We reuse the NULL nodes in the tree.
• We don’t have any difference between threaded node and normal node. :) We can traverse as usual.