THREADED BINARY TREE
A binary tree is represented using array representation or linked list
representation. When a binary tree is represented using linked list representation, if any
node is not having a child we use NULL pointer in that position. In any binary tree linked
list representation, there are more number of NULL pointer than actual pointers.
Generally, in any binary tree linked list representation, if there are 2Nnumberof reference
fields, thenN+1number of reference fields are filled with NULL (N+1 are NULL out of
2N). This NULL pointer does not play any role except indicating there is no link (no
child).
In threaded binary tree, NULL pointers are replaced by references too the r nodes in the
tree, called threads.
A threaded binary tree defined as follows:
"A binary tree is threaded by making all right child pointers that would normally be null
point to the inorder successor of the node (if it exists), and all left child pointers that
would normally be null point to the inorder predecessor of the node."
Why do we need Threaded Binary Tree?
Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers. We can
use the pointers to help us in inorder traversals. Threaded binary tree makes the tree tra-
versal faster since we do not need stack or recursion for traversal.
Comparison between a normal binary tree and threaded binary tree
Types of threaded binary trees:
Single Threaded: each node is threaded towards either the in-order predecessor or succes-
sor (left or right) means all right null pointers will point to inorder successor OR all left
null pointers will point to inorder predecessor.
Double threaded: each node is threaded towards both the in-order predecessor and suc-
cessor(left and right)means all right null pointers will point to inorder successor AND all
left null pointers will point to inorder predecessor.
Single Threaded: each node is threaded towards either the in-order predecessor or succes-
sor (left or right) means all right null pointers will point to inorder successor OR all left
null pointers will point to inorder predecessor.
Implementation:
Let’s see how the Node structure will look like
class
Node{ No
de left;
Noderight;
int data;
boolean rightThread;
publicNode(intdata){
[Link] = data;
rightThread=false;
}
}
In normal BST node we have left and right references and data but in threaded binary tree
we have boolean another field called “right Threaded”. This field will tell whether node’s
right pointer is pointing to its inorder successor, but how, we will see it further.
Operations:
Insert node into tree
Print or traverse the
tree.
Insert():
The insert operation will be quite similar to Insert operation in Binary search tree with
few modifications. To insert a node our first task is to find the place to insert the node.
Take current=root.
Start from the current and compare root. Data with n.
Always keep track of parent node while moving left or right.
if [Link] is greater than n that means we go to the left of the root, if after
moving to left, the current = null then we have found the place where we will
insert the new node. Add the new node to the left of parent node and make the
right pointer points to parent node and right Thread = true for new node.
if [Link] is smaller than n that means we need to go to the right of the root,
while going into the right sub tree, check right Thread for current node, means
right thread is provided and points to the in order successor, if right Thread = false
then and current reaches to null, just insert the new node else if right Thread =true
then we need to detach the right pointer(store the reference, new node right refer-
ence will be point to it)of current node and make it point to the new node and
make the right reference point to stored reference.
Traverse():
Traversing the threaded binary tree will be quite easy, no need of any recursion or any
stack for storing the node. Just go to the left most node and start traversing the tree
using right pointer and whenever right Thread=false a gain go to the left most node in
right sub- tree.
Topological sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering
of vertices such that for every directed edge uv, vertex u comes
before v in the ordering. Topological Sorting for a graph is not possible
if the graph is not a DAG.
For example, a topological sorting of the following graph is “5 4 2 3 1 0”.
There can be more than one topological sorting for a graph. For example,
another topological sorting of the following graph is “4 5 2 3 1 0”. The first
vertex in topological sorting is always a vertex with in-degree as 0 (a vertex
with no in-coming edges).
Algorithm to find Topological Sorting:
In DFS, we start from a vertex, we first print it and then recursively call
DFS for its adjacent vertices. In topological sorting, we use a temporary
stack. We don’t print the vertex immediately, we first recursively call
topological sorting for all its adjacent vertices, then push it to a stack.
Finally, print contents of stack. Note that a vertex is pushed to stack only
when all of its adjacent vertices (and their adjacent vertices and so on) are
already in stack.
The transitive closure of a directed graph is an "extended" version of the graph that shows
all possible reachability relationships between pairs of vertices. It is typically represented as a
Boolean reachability matrix in data structures.
Transitive Closure it the reachability matrix to reach from vertex u to vertex v of a graph.
One graph is given, we have to find a vertex v which is reachable from another vertex u, for
all vertex pairs (u, v).