threaded binary tree

Question

Hello guys i am supposed to write the ThreadedNode() class, but im haveing a few problems with it.

I understand that a threaded binary 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.

however i have my problem starts with the constructor // thread the binary tree when you are given the root public ThreadedNode( BinaryNode root)

i know it receives a binaryNode and i have to make it a threaded tree, but i how do create the new threaded tree?

First calculate the InOrder traversal and keep it store somewhere then traverse the tree and check for the null if null, pick the predecessors or successor from the stored list — Jatin Khurana

ElliotPenson ElliotPenson · Accepted Answer · 2013-04-02T17:11:52

A common way to create threaded binary trees is with a fake head. This makes the single node trees simpler to understand and the constructor more straightforward.

Thus your constructor would probably look like:

public class ThreadedNode {

    private BinaryNode head;

    public ThreadedNode(BinaryNode root) {

        head = new BinaryNode();
        root.makeThreaded();
        root.setRight(head);
        head.setRight(root);

    }
}

Remember that later you need to account for this fake head in insert, delete, etc.

threaded binary tree

1 Answers