Implementation of a threaded binary tree from a binary tree

Question

I am working on a school assignment. This manly consists of a method that takes as input binary tree and returns a double-threaded tree. For example (if left child = null, then the left child will be associated with the previous parent inorder, and if the correct child = null, it will refer to its suorder code. Now I have an idea for implementing ...

I repeat recursively through the original BINARY tree and store the traversal in order in the array. Now, since my teacher implementation requires flow trees to be another binary class. I have to go through the binary tree again and convert each node from binaryNode to threadedNode, thus having at the end a "duplicate" of the original BinaryTree, but as a type of Threadedtree. After that, I go through this threadedTree again, and whenever I see a zero left or right child, I go to the inorder arraylist and find the threads.

Now, as you may have noticed, this is extremely inefficient, I essentially cross the tree 3 times. My professor stated that this can be done recursively with just one workaround, essentially converting to threadedNode and searching for threads at the same time. I tried several ways, but I can not find the one that works. Does anyone have any hint or somehow can I implement it? Thanks

This is the method indicated by the instructor.

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

Answer 1

The instructor is faithful. One round is enough.

Trace the source binary tree, creating a new ThreadedNode while traversing 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 that you bypassed is D. There is no previous node. Therefore, save D as the previous one. Then the next node you press B. The previous node was D, which did not have the right child, so add the desired pointer to the right of D to B. Then set the previous option B and continue. Then you press A. B does not have the right child, so add the right link to the right of B to A. A has the right child, so continue by setting the previous value A. The next node is C. C does not have a left child, so add a threaded left link from C to the current value of the previous one, which is equal to A.

Answer 2

You can skip the second round trip that you mentioned in your method. You can convert nodes from BinaryNode to ThreadedNode on the fly. In my opinion, you would need to go through twice to get around the order, and to search for streams and convert it to aThreadedTree.

To convert on the fly, you can use the method your instructor gave.

NTN!