4

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
}
Improve this question

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

I thought about doing that, but remember that I also must create a new threadedNode for each node visited since there is a difference between binaryNode and threadedNode. So I must build the ThreadedTree while doing the inorder traversal of the initial Binarytree.
Definitely! Emit threaded nodes as you go. I can update my answer if you like.
I understand your implementation, there is a small problem with your code (right null children does not seem to thread) but now I know where to start. Thank you
Oh sorry I should have tested it. Let me know if you get stuck. Glad it is a starting point, though.
I think I am done, I have to test with different trees to make sure. I resorted to using recursion but aside from having the holder for the previous element I also had a stack that would allow me to find the next element and append it to the right children before the recursive call ended. Can't thank you enough for your help. Have a Gn.
|
0

You could skip the second trip of traversal that you mention in your method. You could convert the nodes from BinaryNode to ThreadedNode on the fly. You'd still need to traverse twice, I think, for the inorder traversal, and for finding the threads and converting it to aThreadedTree.

For conversion on the fly, you could use the method that your instructor has given.

HTH!

Improve this answer

1 Comment

What do you mean by converting on the fly?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.