Module 3 Data Structures and Applications (BCS304)

MODULE 3
Additional List Operations
1. Inverting a singly linked list:
Inverting or reversing a chain (list) is use to reverse the list and can be done by using 3 pointers
(trail, middle and lead). Invert function is as given below
listpointer invert(listpointer lead)
{
listpointer middle,trail;
middle=null;
while(lead)
{
trail=middle;
middle=lead;
lead=lead->link;
middle->link=trail;
}
return middle;
}

2. Concatenating singly linked lists:

Concatenation of two list is as follow
listpointer concatenate(listpointer ptr1,listpointer ptr2)
{
if(!ptr1) return ptr2;
if(!ptr2) return ptr1;

temp=ptr1;
while(temp->link!=NULL)
temp=temp->link;

temp->link=ptr2;
}

Operations for Circularly Linked Lists:

Circular list is a list where the last node contains the address of the first node in its link
field. ‘last’ be the pointer to the last node in the list rather than to the first node. This makes
inserting and deleting at first and last easy.
Inserting at front of the list:
To insert a node at the front of a circular list is as follow. To insert at the rear (end) we only need
to add the additional statement last =node to else clause of insertFront function
void insertfront(listpointer* last,listpointer node)
{
if(!(*last))
{
*last=node;
}

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 1

Module 3 Data Structures and Applications (BCS304)
else
{
Node->link = (*last)->link;
(*last)->link=node;
}
}

2. Finding the length of a circular list

Function to calculate number of nodes in a list is as follow

int length(listpointer last)
{
listpointer temp;
int count=0;
if(last!=NULL)
{
temp=last;
do
{
count++;
temp=temp->link;
}while(temp!=last);
}
return count;
}
Sparse matrix representation
In data representation, each column of a sparse matrix is represented as a circularly linked list
with a header node. A similar representation is used for each row of a sparse matrix. Each node
has a tag field, which is used to distinguish between header nodes and entry nodes.
Header Node:
 Each header node has three fields: down, right, and next as shown in figure(a).
 The downfield is used to link into a column list and the right field to link in to a row list.
 The next field links the header nodes together.
 The header node for row i is also the header node for column i, and the total number of
header nodes is max{number of rows, number of columns}.
Element node:
 Each element node has five fields in addition to the tag field: row, col, down, right,
value as shown in figure (b).
 The down field is used to link to the next non zero term in the same column and the
right field to link to the next non zero term in the same row. Thus, if aij ≠0, there is a
node with tag field = entry, value = aij, row = i, and col = j as shown in figure (c).

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 2

Module 3 Data Structures and Applications (BCS304)
 We link this node into the circular linked lists for row i and column j. Hence, it is
simultaneously linked into two different lists.

Figure 1: node representation

Consider the sparse matrix, as shown in the below figure(2).

Figure 2: Sparse Matrix

Figure below shows the linked representation of above matrix. Although we have not shown
the value of the tag fields, we can easily determine these values from the node structure.
For each nonzero term of a, have one entry node that is inexactly one row list and one column
list. The header nodes are marked HO-H3. As the figure shows, we use the right field of the
header node list header.

Figure 3: linked list representation of sparse Matrix

To represent a numRows x numCols matrix with numTerms non zero terms, then we need
max{numRows,numCols}+numTerms+[Link] each node may require several words of
memory, total storage will be less than numRows x numCols when numTerms is sufficiently small.
There are two different types of nodes in representation, so unions are used to create the
appropriate data structure. The C declarations are as follows:

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 3

Module 3 Data Structures and Applications (BCS304)
#define SIZE 50
typedef enum {head,entry};
tyepdef struct matrixNode *matrixPoiner;
typedef struct
{
int row;
int col;
int value;
}entryNode;
typedef struct
{
matrixPointer down;
matrixPointer right;
tagfield tag;
union
{
matrixPointer next;
entryNode entry;
}u;
}matrixNode;
matrixPointer hdnode[SIZE];

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 4

Module 3 Data Structures and Applications (BCS304)

Doubly Linked List (DLL)

Disadvantages of SLL
Possible to traversal only in one direction, ie., direction of the links.
 The only way to find the node that precedes is to start at the beginning of the list.
 These problems can be overcome by using doubly linked list
Doubly linked list: is a linear collection of data elements, called nodes, where each node
has three parts:
1. An information field ‘data’ which contains the data of a node
2. A pointer field llink which contains the address of the next node in the list
3. A pointer field rlink which contains the address of the preceding node in the list
struct node
{
int data;
struct node llink;
struct node rlink’
};
typedef struct node *NODEPTR;

Insertion into a doubly linked list

Insertion into a doubly linked list is fairly easy. Assume there are two nodes, node and new
node, node may be either a header node or an interior node in a list. The function dinsert performs
the insertion operation in constant time.

Deletion from a doubly linked list

Deletion from a doubly linked list is equally easy. The function ddelete deletes the node
deleted from the list pointed to by node. To do this deletion, we only need to change the link
fields of the nodes that precede (deleted→llink→rlink) and follow(deleted→rlink→llink) the
node we want to delete.

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 5

Module 3 Data Structures and Applications (BCS304)

Trees
A tree is a finite set of one or more nodes such that
 There is a specially designated node called root.
 The remaining nodes are partitioned into n>=0 disjoint set T1,…,Tn,where
each of these sets is a tree. T1,…,Tn are called the subtrees of the root.

Level
1

4
Figure 4: Binary tree

Every node in the tree is the root of some subtree.

1. Root node: In a tree data structure, the first node is called as Root Node. Every tree must
have a root node. We can say that root node is the origin of tree data structure. In any tree,
there must be only one root node. Ex: ‘A’ in the above tree
2. Edge: Connecting link between any two nodes is called as edge. In a tree with 'N' number of
nodes there will be a maximum of 'N-1' number of edges. Ex: Line between two nodes.
3. Parent: node which is predecessor of any node is called as parent node. In simple words, the
node which has branch from it to any other node is called as parent node. Ex: A,B,C,D are
parent nodes
4. Child: the node which is descendant of any node is called as child node. In a tree, any parent
node can have any number of child nodes. In a tree, all the nodes except root are child nodes.
Ex: B, C and D are children of A.
5. Siblings: Nodes which belong to same Parent are called as siblings. Ex: B, C and D are
siblings.

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 6

Module 3 Data Structures and Applications (BCS304)
6. Leaf: Node which does not have a child is called as leaf Node (also called as External
Nodes). External node is also a node with no child. Leaf node is also called as 'Terminal'
node. Ex: K,L, F, G, M, I, J
7. Internal Nodes: Node which has at least one child is called as internal node. Nodes other
than leaf nodes are called as Internal Nodes. The root node is also said to be Internal Node if
the tree has more than one node. Internal nodes are also called as 'Non-Terminal' nodes. Ex:
A, B, C, D, E and H
8. Degree of a node : total number of children of a node is called as degre of that Node. The
highest degree of a node among all the nodes in a tree is called as 'Degree of Tree'. Ex:
Degree of A is 3, B is 2 and of C is 1, K is 0
9. Level of a node : the root node is said to be at Level 1 and the children of root node are at
Level 2 and so on...
10. Height: In a tree data structure, the total number of edges from leaf node to a particular
node in the longest path is called as height of that Node. In a tree, height of the root node
is said to be height of the tree. In a tree, height of all leaf nodes is '0'.
11. Depth: The total number of edges from root node to a particular node is called as
DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in
the longest path is said to be Depth of the tree. In simple words, the highest depth of any
leaf node in a tree is said to be depth of that tree. In a tree, depth of the root node is '0'.
12. Path: In a tree data structure, the sequence of Nodes and Edges from one node to
another node is called as path between the two Nodes. Length of a Path is total number of
nodes in that path. Example the path A - B - E - K has length 4.
13. Ancestor: The ancestors of a node are all the nodes along the path from the root to that
node. Ex: ancestor of E is B & A
General Tree Representations
A general Tree Structure can be represented with the following three methods. List
Representation

1. List Representation
2. Left Child-Right Sibling Representation
3. Degree two Representation (Binary Tree Representation)

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 7

Module 3 Data Structures and Applications (BCS304)

1. List Representation
There are several ways to draw a tree. One useful way is as a list. The tree in the above figure
could be written as the list

(A(B(E(K,L),F),C(G),D(H(M),I,J)))

list representation (with rounded brackets).The information in the root node comes first
followed by a list of the subtrees of that node. Now, how do we represent a tree in memory?
If we wish to use linked lists, then a node must have a varying number of fields depending
upon the number of branches.

Figure 5: List representation of binary tree

Possible node structure for a tree of degree k called k-ary tree

Data link1 link2 ....... linkk

Each link field is used to point to a subtree. This node structure is cumber some for the
following reasons (1) Multiple node structure for different tree nodes (2) Waste of space (3)
Excessive use of links. The other alternate method is to have linked list of child nodes which
allocates memory only for the nodes which have children. In this representation, we use two
types of nodes, one for representing the node with data and another for representing only
references. We start with a node with data from root node in the tree. Then it is linked to an
internal node through a reference node and is linked to any other node directly. This process
repeats for all the nodes in the tree.

2. Left Child –Right Sibling Representation

In this representation, we use list with one type of node which consists of three fields namely
Data field, Left child reference field and Right sibling reference field.

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 8

Module 3 Data Structures and Applications (BCS304)
To convert the tree of Figure above into this representation:
1. First note that every node has atmost one left most child
2. Atmost one closest right sibling.
Data

Left Right
child sibling

 In Figure 4, the leftmost child of A is B, and the leftmost child of D is H.

 The close straight sibling of B is C, and the closest right sibling of H is I.
 Choose the nodes based on how the tree is drawn. The left child field of each node points to its
leftmost child (ifany), and the right sibling field points to its closest right sibling (if any).
 Figure 6 shows the tree of Figure 4 redrawn using the leftchild-rightsibling representation.

Figure 6: Left child – right sibling representation of binary tree

3. Degree two tree (BinaryTree)

To obtain the degree-two tree representation of a tree, simply rotate the right-sibling pointers in a
left child-right sibling tree clock wise by 45 degrees. This gives us the degree- two tree displayed
in Figure 7.

Figure 7: Degree two representation of binary tree

In the degree-two representation, a node has two children as the left and right children.

Binary trees
Definition: A binary tree T is defined as a finite set of nodes such that,
 T is empty or
 T consists of a root and two disjoint binary trees called left sub tree and right subtree.

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 9

Module 3 Data Structures and Applications (BCS304)

Figure 8: Binary tree

Different kinds of Binary Tree

1. Skewed Tree
A skewed tree is a tree, skewed to the left or skews to the right. Or It is a tree consisting of only
left subtree or only right subtree.
 A tree with only left subtrees is called Left Skewed BinaryTree.
 A tree with only right subtrees is called Right Skewed BinaryTree.
2. Complete Binary Tree
A binary tree T is said to complete if all its levels, except possibly the last level, have the
maximum number node 2i,i≥0 and if all the nodes at the last level appears as far left as possible.

3. Full BinaryTree
A full binary tree of depth ‘k’is a binary tree of depth k having 2k–1nodes,k≥1.

Figure 9: Full binary tree of level 4 with sequential node number

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 10

Module 3 Data Structures and Applications (BCS304)

4. Extended Binary Trees or 2-trees

An extended binary tree is a transformation of any binary tree into a complete binary tree.
This transformation consists of replacing every null subtree of the original tree with “special
nodes. ”The nodes from the original tree are then internal nodes, while the special nodes are
external nodes.
consider the following binary tree.

Figure 10 : Binary tree and Extended Binary Tree

In extended binary tree, circles represent internal nodes, and square represent external nodes.
Every internal node in the extended tree has exactly two children, and every external node is a
leaf. The result is a complete binary tree.
Properties of binary trees
Lemma1:[Maximum number of nodes]:
(1) The maximum number of nodes on level i of a binary tree is 2i-1,i≥1.
(2) The maximum number of nodes in a binary tree of depth k is 2k -1,k≥1.
Proof:
(1) The proof is by induction on i.
Induction Base: The root is the only node on level i = 1. Hence, the maximum number of

nodes on level i =1 is 2 i-1= 20= 1.

Induction Hypothesis: Let i be an arbitrary positive integer greater [Link] that the

maximum number of nodes on level i -1is 2i-2

Induction Step: The maximum number of nodes on level i -1 is 2i-2by the induction
hypothesis. Since each node in a binary tree has a maximum degree of 2, the maximum number
of nodes on level i is two times the maximum number of nodes on level i-1, or 2i-1

(2) The maximum number of nodes in a binary tree of depth k is k

K∑(maximum number of nodes on level i)=∑2i-1=2k-1i=0i=0

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 11

Module 3 Data Structures and Applications (BCS304)

Lemma2:[Relation between number of leaf nodes and degree-2nodes]:

For any non empty binary tree, T, if n0 is the number of leaf nodes and n2 the number of nodes
of degree 2, then n0= n2+ 1.
Proof: Let n1 be the number of nodes of degree one and n the total number of nodes.
Since all nodes in T are atmost of degree two, we have
n=n0+n1+n2 (1)
Count the number of branches in a binary tree. If B is the number of branches, then n =B + 1.
All branches stem from a node of degree one or two. Thus,
B=n1+2n2.
Hence, we obtain
n= B+1 = n1 + 2n2 + 1 (2)
Subtracting Eq.(2) from Eq.(1) and rearranging terms, we get
n0=n2+1
Consider the figure:

Figure 11 : Binary tree

Here, For Figure (b) n2=4,n0=n2+1=4+1=5 Therefore, the total number of leaf node=5

Binary tree representation

The storage representation of binary tree scan be classified as
1. Array representation
2. Linked representation.

Array representation:
 A tree can be represented using an array, which is called sequential representation.
 The nodes are numbered from1t on, and one dimensional array can be used to store the nodes.
 Position0 of this array is left empty and the node numbered i is mapped to position i of the
array.

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 12

Module 3 Data Structures and Applications (BCS304)

Below figure shows the array representation for both the trees of figure(a).

 For complete binary tree the array representation is ideal, as no space is wasted.
 For the skewed tree less than half the array is utilized.

Linked representation:
The problems in array representation are:
 It is good for complete binary trees, but more memory is wasted for skewed and many
other binary trees.
 The insertion and deletion of nodes from the middle of a tree require the movement of
many nodes to reflect the change in level number of these nodes.

These problems can be easily over come by linked representation Each node has three fields,
 LeftChild -which contains the address of left subtree
 RightChild- which contains the address of right subtree.
 Data -which contains the actual information

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 13

Module 3 Data Structures and Applications (BCS304)

Representation of node:

Typedef struct node* treepointer;

typedef struct
{
int data;
treepointer leftChild,rightChild;
}node;

Binary tree traversals

Visiting each node in a tree exactly once is called tree traversal The different methods of
traversing a binary tree are:
1. Preorder
2. Inorder
3. Postorder
4. Level-Order traversal

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 14

Module 3 Data Structures and Applications (BCS304)

1. Inorder: calls for moving down the tree toward the left until you cannot go further. Then
visit the node, move one node tothe right and continue. If no move can be done, then go back
one more node.

The inorder traversal of a binary tree can be recursively defined as

 Traverse the left subtree in inorder.
 Visit the root.
 Traverse the right subtree in inorder.
voidinorder(treepointerptr)
{
if(ptr)
{
inorder (ptr→leftchild);
printf (“%d”,ptr→data);
inorder(ptr→rightchild);
}
}

Figure 12 : Expression tree of expression “A/B*C*D+E

Tracing of the above recursive function is given in the below table for figure 12
Call of Value of Action Call of inorder Value of root Action
inorder root
1 + 11 C
2 * 12 NULL
3 * 11 C printf
4 / 13 NULL
5 A 2 * printf
6 NULL 14 D
5 A printf 15 NULL
7 NULL 14 D printf
4 / printf 16 NULL
8 B 1 + printf
9 NULL 17 E
8 B printf 18 NULL
10 NULL 17 E printf
3 * printf 19 NULL

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 15

Module 3 Data Structures and Applications (BCS304)

2. Preorder: Preorder is the procedure of visiting a node, traverse left and continue. When
you cannot continue, move right and begin again or move back until you can move right
and resume.

The Preorder traversal of a binary tree can be recursively defined as

 Visit the root
 Traverse the left subtree in preorder.
 Traverse the right subtree in preorder

void preorder(treepointer ptr)

{
if(ptr)
{
printf (“%d”,ptr→data);
preorder (ptr→leftchild);
preorder(ptr→rightchild);
}
}
3. Postorder: Postorder traversal calls for moving down the tree towards the left until you
can go no further. Then move to the right node and then visit the node and continue. The
Postorder traversal of a binary tree can be recursively defined as

• Traverse the left subtree in postorder.

• Traverse the right subtree in postorder.
• Visit the root
voidpostorder(treepointerptr)
{
if(ptr)
{
postorder (ptr→leftchild);
postorder (ptr→rightchild);
printf (“%d”,ptr→data);
}
}

4. Iterative inorder Traversal:

Iterative inorder traversal explicitly makes use of stack function.

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 16

Module 3 Data Structures and Applications (BCS304)
The left nodes are pushed into stack until a null node is reached, the node is then removed
from the stack and displayed, and the node ’sright child is stacked until a null node is
reached. The traversal then continues with the left child. The traversal is complete when the
stack is empty.

5. Level-Order traversal:
Visiting the nodes using the ordering suggested by the node numbering is called level
ordering traversing. The nodes in a tree are numbered starting with the root on level 1 and
soon. First visit the root, then the root’s left child, followed by the root’s right child. Thus
continuing in this manner, visiting the nodes at each new level from the left most node to the
right most node.

Initially in the code for level order add the root to the queue. The function operates by
deleting the node at the front of the queue, printing the nodes data field and adding the nodes
left and right children to the queue. Function for level order traversal of a binary tree is:

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 17

Module 3 Data Structures and Applications (BCS304)

Threaded binary tree

The limitations of binary tree are:
 Inbinarytree,therearen+1nulllinksoutof2ntotallinks.
 Traversing a tree with binary tree is time consuming. Theselimitations can be
overcome by threaded binary tree.
In the linked representation of any binary tree, there are more null links than actual pointers.
These null links are replaced by the pointers, called threads, which points to other nodes in the
tree.
To construct the threads use the following rules:
1. Assume that ptr represents a node. If ptr→leftChild is null, then replace the null link with a
pointer to the inorder predecessor of ptr.
2. If ptr→rightChild is null, replace the null link with a pointer to the inorder successor of ptr.
Ex: Consider the binary tree as shown in below figure:

Figure 13 : Binary tree

There should be no loose threads in threaded binary tree. But in Figure 14 two threads
have been left dangling: one in the left child of H, the other in the rightchild of G.

Figure 14 : Threaded Binary tree for Figure 13

In above figure the new threads are drawn in broken lines. This tree has 9 node and 10- links
which has been replaced by threads.

When trees are represented in memory, it should be able to distinguish between threads and
pointers. This can be done by adding two additional fields to node structure, ie., leftThread
and rightThread

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 18

Module 3 Data Structures and Applications (BCS304)

 If ptr→leftThread =TRUE, then ptr→leftChild contains a thread, otherwise it contains a

pointer to the left child.
 If ptr→right Thread=TRUE, then ptr→rightChild contains a thread, otherwise it contains
a pointer to the right child.
Node Structure:
The node structure is given in C declaration
typedef struct threadTree* threadPointer
typedef struct
{
Short int leftThread;
threadPointer leftChild;
char data;
threadPointer rightChild;
short int rightThread;
}threadTree;

The complete memory representation for the tree of figure is shown in Figure 15
The variable root points to the header node of the tree, while root→leftChild points to the start
of the first node of the actual tree. This is true for all threaded trees. Here the problem of the
loose threads is handled by pointing to the head node called root.

Figure 15 :Empty Threaded Binary tree

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 19

Module 3 Data Structures and Applications (BCS304)

Inorder Traversal of a Threaded Binary Tree

 By using the threads, an inorder traversal can be performed without making use of a stack.
 For any node, ptr, in a threaded binary tree, if ptr→rightThread =TRUE, then inorder
successor of ptr is ptr →rightChild by definition of the threads. Otherwise we obtain the
inorder successor of ptr by following a path of left-child links from the right-Child of ptr
until we reach a node with leftThread=TRUE.

 The function insucc ( ) finds the inorder successor of any node in a threaded tree without
using a stack.
threadedpointer insucc(threadedPointer tree)
{ threadedpointer temp;
temp=tree→rightChild;
if (!tree→rightThread)
while (!temp→leftThread)
temp=temp→leftChild;
returntemp;
}
To perform inorder traversal make repeated calls to insucc( )function

voidtinorder(threadedpointertree)
{
threadedpointer temp=tree;
for(; ;)
{
temp=insucc(temp);
if(temp==tree)break;
printf(“%3c”,temp→data
}
}

Inserting a Node into a Threaded Binary Tree

In this case, the insertion of ‘r’ as the rightchild of a node ‘s’ is implemented.
The cases for insertion are:
 If s has an empty rightsubtree, then the insertion is simple and diagrammed in Figure 16 (a)
 If the right subtree of s is not empty, then this rightsubtree is made the rightsubtree of r after
insertion as in Figure 16 (b). When this is done, r becomes the inorder predecessor of a node that
has a leftThread ==truefield, and consequently there is a thread which has to be updated to
point to r. The node containing this thread was previously the inorder successor of s.

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 20

Module 3 Data Structures and Applications (BCS304)

Figure 16 : (a) and (b)

Void insertRight(threadedPointer Sf,threadedPointer r)

{
threadedpointer temp;
r→rightChild = parent→rightChild;
r→rightThread =parent→rightThread;
r→leftChild = parent;
r→leftThread = TRUE;
s→rightChild = child;
s→rightThread=FALSE;
if (!r→rightThread)
{
temp= insucc(r);
temp→leftChild=r;
}
}

Dr. Sunitha M R, Prof. & Head, AIML, AIT, CKM Page 21