Wednesday, 15 June 2011

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.”


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

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.


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!!


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, 



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.


Tree* makeThreaded(Tree* root)
    if(root == NULL)
        return NULL;
    Tree* leftPrev = makeThreaded(root->left);
    if(leftPrev != NULL) {
        Tree* iter = leftPrev;
        while(iter->right != NULL && iter->right != leftPrev)
            iter = iter->right;
        iter->right = root;
    Tree* rightPrev = makeThreaded(root->right);
    if(rightPrev != NULL) {
        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.