Threaded Binary tree implementation from binary tree

Question

I am working on assignment for school. It manly consists of a method that takes as input a binary tree and returns a double threaded tree. Eg(if left child = null then left child will be connected with preceding inorder parent and if right child = null the it will link to its inorder succesor. Now I have an idea for the implementation...

I iterate recursively trough the original BINARY tree and store into an array the inorder traversal. Now, because my teachers implementation requires that threaded trees be a different class from binary. I must traverse again trough the binary tree and convert each node from binaryNode to threadedNode thus having at the end a "duplicate" of the initial BinaryTree but as Threadedtree type. After I do this I traverse again trough this threadedTree and whenever i see a null left or right child I refer to the inorder arraylist and find the threads.

Now as you might have noticed this is extremely inefficient, i am essentially traversing the tree 3 times. My professor has stated that this could be done recursively with only one traversal, essentially converting to threadedNode and finding the threads all at once. I have tried multiple ways but i can not find one that works. Does anyone have any kind of tip or some way i can implement it? Thanks

This is the method as specified by the instructor

public static <T> ThreadedNode<T> thread(BinaryNode<T> root)
{
   //threads a binary tree
}

Ray Toal Ray Toal · Accepted Answer · 2011-11-30T06:26:58

The instructor is correct. One traversal is sufficient.

Traverse the original binary tree, creating new ThreadedNodes as you walk this tree.

public static <T> ThreadedNode<T> thread(BinaryNode<T> root) {
    // We'll be keeping track of the "previous" node as we go, so use
    // a recursive helper method.  At first, there is no previous.
    return threadHelper(root, null);
}

private static <T> ThreadedNode<T> threadHelper(BinaryNode<T> n, ThreadedNode<T> previous) {

    // Create a new threaded node from the current root.  Note that the threaded nodes
    // are actually created in "preorder".  Assume the ThreadedNode constructor sets
    // the left, right, threadLeft, and threadRight fields to null.
    ThreadedNode<T> t = new ThreadedNode<T>(n.getData());

    // First go down the left side, if necessary.
    if (n.getLeft() != null) {
        // If there is a left child we have to descend.  Note that as we go down the
        // left side the previous doesn't change, until we start "backing up".
        t.left = threadHelper(n.getLeft(), previous);
        previous = t.left;
    } else {
        // If there is no left child, connect our left thread to the previous.
        t.threadLeft = previous;
    }

    // Now before we go down the right side, see if the previous
    // node (it will be in the left subtree) needs to point here.
    if (previous != null && previous.right == null) {
        previous.threadRight = t;
    }

    if (n.getRight() != null) {
        // If there is a right child we can descend the right.  As we go down we
        // update previous to the current node.  We do this just by passing the current
        // node as the second parameter.
        t.right = threadHelper(n.getRight(), t);
    } else {
        // No right child, no worries.  We'll hook up our thread-right pointer
        // later.
    }
    return t;
}

Consider the tree (A (B (D) ()) C). The first node you hit in an inorder traversal is D. There is no previous node. So save D as previous. Then the next node you hit is B. The previous node was D, which had no right child, so add a threaded right pointer from D to B. Then set previous to B and continue. Next you hit A. B had no right child, so add a threaded right link from B to A. A has a right child so continue, setting previous to A. The next node is C. C has no left child, so add a threaded left link from C to the current value of previous, which is A.

Threaded Binary tree implementation from binary tree

2 Answers