CODEWITHSUNDEEP
javabinary-tree
Lexy Feito
Lexy Feito

Reputation: 290

threaded binary tree

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?

Upvotes: 1

Views: 1018

Answers (1)

ElliotPenson
ElliotPenson

Reputation: 364

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.

Upvotes: 0

Related Questions