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....😀
4.7k views

Related Posts

@imgopi · Sep 4, 2011

Hi am fresher doing btech(cse) i want to join in infosys plz help me to get success in interview.
5.6k views

@akshay gopi · Feb 22, 2015

Project Abstract / Summary : AUTOMATIC SPEED CONTROL IN AUTOMOBILES ABSTRACT Speed control is in the need of the hour due to the increased rate of accidents reported in our...
8.4k views

@Ak_Sabbath · Aug 4, 2015

Hello, All I'm a 2015 ECE batch passout. I am planning to join Software manual testing and automation course as I can't afford to join any ECE core courses. I...
4.6k views

@Ankita Katdare · Nov 26, 2013

The year 2013 has been a great one for Micromax Mobiles, one of the biggest consumer electronics company in India, as the country witnessed the launch of a series of...
13.1k views

@adi · Oct 11, 2006

hi guys i m doing BE in electronics and communication and i want some suggestions. which is better frm job point of view .net or CCNA.
3.1k views