CrazyEngineers Archive
Old, but evergreen and popular discussions on CrazyEngineers, presented to you in read-only mode.
@Ankita Katdare • 26 Dec, 2010
In the linked representation of a binary tree, additional space is required to store the two links of each node.
For leaf nodes, these fields always have nil values as there are no left or right sub-trees present.
To remove this drawback of memory wastage, the concept of threaded binary tree was developed. In this type of tree, the empty links are replaced by pointers, called threads which point to some other node of the tree.

If the left child of a node of a tree is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just before that node, when the tree is traversed in inorder.

Similarly, if a right child of the node is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just after that node, when the tree is traversed in inorder.
Such threads are called inorder threads.
We also have preorder and postorder threads.

The left thread gives predecessor and the right thread gives successor node.

The node of a threaded binary tree can be declared as:

enum boolean
{
int false = 0;
int true = 1;
};
struct threadedtree
{
enum boolean left;
struct threadedtree *leftchild;
int data;
enum boolean right;
struct threadedtree *rightchild;
}
@Sachin Jain • 26 Dec, 2010 Hey AbraKaDabra Thanks for this topic...its really good and helpful.
I had never observed about the wastage due null pointers in leaf nodes.
-
Can you please explain this line:-
If the left child of a node of a tree is null (or empty) it will be replaced by a thread (i.e. a pointer) to that node which appears just before that node, when the tree is traversed in inorder.
What is the advantage of doing so ?

Any appliaction of threaded binary trees ?

Thanks in advance...
@Ankita Katdare • 26 Dec, 2010 Good Question. Following are the advantages of using threaded binary tree:

1) The traversal operation is faster than that of its unthreaded version, because with threaded binary tree non-recursive implementation is possible which can run faster and does not require the botheration of stock management.

2) We can efficiently determine the predecessor and successor nodes starting from any node. A stack is required to provide upward pointing information in the tree whereas in a threaded binary tree, without having to incur the overload of using a stack mechanism the same can be carried out with the threads.

3) Any node can be accessible from any other node. Threads are usually more to upward whereas links are downward. Thus in a threaded tree, one can move in either direction and nodes are in fact circularly linked. This is not possible in unthreaded counter part because there we can move only in downward direction starting form root.

4) Insertion into and deletions from a threaded tree are all although time consuming operations(since we have to manipulate both links and threads). But these are very easy to implement.
@Sachin Jain • 26 Dec, 2010 Thanks AbraKaDabra very nicely explained....😀
6.1k views

Related Posts

@Ankita Katdare · Dec 1, 2012

Electrical Engineers here can Gather! Here is a thread dedicated to listing down and discussing all the internship opportunities in India in any city for the Summer of 2013. Those...
4.4k views

@Ankita Katdare · Oct 10, 2014

It's common knowledge that when Xiaomi Redmi 1S arrived in India, the news of its launch spread like wildfire. The flash sale model on Flipkart was a big hit and...
12.1k views

@Ankita Katdare · Sep 5, 2013

India Kawasaki Motors (IKM), the subsidiary of the Japanese company, is here to create much fanfare with the launch of two brand new bikes in India. With the set up...
10k views

@Ankita Katdare · Oct 7, 2015

Microsoft has announced the India launch for its new Windows Phone 8.1 with Lumia Denim smartphone called - Microsoft Lumia 640 XL LTE Dual SIM. The phone was first unveiled...
4.5k views

@rakesh.v.1987 · Aug 27, 2009

hey i'm thinking of doing an M.S in engineering management in the U.S. does this course have scope now.. is it a safe option now. please help
10k views