double threaded tree from binary tree

Question

I need to build a double threaded tree from a regular binary tree, using recursion if possible. This is the definition that we are usig: The threaded tree of a binary tree is obtained by setting every null left child to the predecessor of the node in the inorder traversal and every null right child to the successor of the node in the inorder traversal.

I cant find a solution to this and there are a couple of posts similar to this one here but without a solution. I just need the algorithm, it can be in any language

This are the constructors, the 2nd one is the one I need to do:

public ThreadedNode(T theElement, ThreadedNode<T> lt, ThreadedNode<T> rt)
{
    element = theElement;
    left = lt;
    right = rt;
}

public ThreadedNode( BinaryNode<T> root)
{
    // implement it 
}



 //the fields

  private T element; 

  private boolean lThread = false;

  private ThreadedNode<T> left; 

  private boolean rThread = false;

  private ThreadedNode<T> right; 

}

my initial approach is to call a helper method, recursively, like this:

ThreadNode<T> helper(BinaryNode<T> n, BinaryNode<T> predecessor, BinaryNode<T> successor)

, initially predecessor and successor are null, but then as I go down traversing the tree in_order I set them using the current node and its parent, depending on whether it is a left or right child but I think it does not work for all the cases and I cant see how to improve it

thank you in advance

The left pointer is easy enough. The right pointer is a bit more difficult. See analgorithmaday.blogspot.com/2011/06/…. Also stackoverflow.com/questions/1202053/… — Jim Mischel
Thank you a lot Jim, I will "add" the logic from the 2 links that you provided, I haven't found yet an algorithm for the double threaded tree. — user1742444

Rikayan Bandyopadhyay Rikayan Bandyopadhyay · Accepted Answer · 2014-04-15T06:42:25

Since you mentioned that it can be any language, here is a C implementation provided along with very good explanation.

double threaded tree from binary tree

1 Answers