Module 3

1
Module 3
• LINKED LISTS :
• Additional List Operations, Sparse Matrices, Doubly Linked List.
• TREES:
• Introduction, Binary Trees, Binary Tree Traversals, Threaded Binary Trees.

2
LINKED LISTS (contd.)

3
Concatenating Singly Linked (Concatenating two chains)
struct list{ NODE *concatenate(NODE *l1,NODE *l2){
int data; NODE *t;
struct list*link; if(!l1)
}; return(l1);
typedef struct list NODE; else if(!l2)
return(l2);
else
for(t=l1;t->link;t=t->link);
t->link=l2;

return(l1);
}

4
Inverting Singly Linked (Inverting two chains)
NODE *Invert(NODE *l){
struct list{
NODE *result=NULL, *t1=result;
int data;
while(l){
struct list*link;
t=l;
};
l=l->next;
typedef struct list NODE;
t->link=t1;
t1=t;
}
return(result);
}

5
Insertion of a node at front of circular linked
list NODE *Front_circular(NODE *list,NODE *temp){
if(!list)
struct list{ {
int data; list=temp;
temp->link=list;
struct list*link; }
}; else{
temp->link=list->link;
typedef struct list NODE; list->link=node;
}
return(list);
}

6
Finding length of circular linked list
struct list{ int count (NODE *list){
int data; NODE *temp=list;
int count=0;
struct list*link;
if (list)
};
temp=list;
typedef struct list NODE; do{
count++;
temp=temp->link;
}while(temp!=list);
return(count);
}

7
Sparse Matrix

8
Sparse matrix : Linked Representation
• Linked list data structure is used to represent a sparse matrix.
• In this linked list, two different nodes namely header node and element
node are used.
• Header node consists of three fields and element node consists of five
fields.
• This sparse matrix can be represented using linked representation as shown
in the below image.

9
C structure representation
struct sparseMatrix{
union{
struct NODEPTR * Next;
struct entry{
int row,col,value;
}data;
} u;
struct sparseMatrix *down,*right;
};
typedef struct sparseMatrix NODE;
NODE * Head;

11/28/2024 10
0 0 0 0 9 0
0 8 0 0 0 0
4 0 2 0 0 0
0 0 0 0 0 5
0 0 2 0 0 0

5 6 6
0 4 9
1 1 8
2 0 4
2 2 2
3 5 5
4 2 2

11
Doubly Linked List

12
Two way list-Doubly linked list
• Using singly list we can only traverse in one direction. i.e we
can only access next node but not previous node.
• In two way list ,the list can be made accessible in both
direction..
• Each node N is divided into three parts
• An information field INFO which contains the data of N
• A pointer field FORW or RIGHT which contains address of next node
• A pointer field BACK or LEFT which contains address of previous node

11/28/2024 13
14
DLL: Data structure requirements
Let LOCA and LOCB are two pointers of nodes A and B such that
LOCARight=LOCB
LOCBLeft=LOCA
LOCA LOCB
struct Data{ NODE* Getnode(){
int item; NODE *node=(NODE*)calloc(1,sizeof(NODE));
printf("\nEnter item:");
struct Data *Llink,*Rlink; scanf("%d",&node->item);
}; return (node);
}
typedef struct Data NODE;

void Display(NODE *p){ //traversing

while(p!=NULL){
printf("\n%d\n", p->item);
p=p->Rlink;
}
}
11/28/2024 15
 Front- and Rear Insertions
NODE* Insert_Front(NODE *head){ NODE* Insert_Rear(NODE *head){
NODE *p=head, *newnode; NODE *p=head, *newnode;
newnode=Getnode(); newnode=Getnode();
if(head= =NULL) if(head= =NULL)
head=newnode; head=newnode;
else{
else{
while(p->right!=NULL){
newnode->right=head;
p=p->right;
head->left=newnode;
}
head=newnode; p->right=newnode;
} newnode->left=p;
} }
return head; return head;
} }

11/28/2024 16
Rear and Front Deletions
NODE* Delete_Rear(NODE *head){ NODE* Delete_Front(NODE *head){
NODE *p=head,*q; NODE *p=head,*q;
if(head= =NULL)
if(head= =NULL)
printf("\nList is Empty (QUEUE)");
printf("\nList is Empty (QUEUE)");
else {
else {
while(p->right!=NULL)
p=p->right;
if( p->right = =NULL)
if( p->left !=NULL){ head=NULL;
q=p->left; else{
q->right=NULL; head=head->right;
} head->left=NULL;
else }
head=NULL; }
free(p);
return head;
}
}
return head;
}

11/28/2024 17
Trees

18
• TREES: Introduction, Binary Trees, Binary Tree Traversals, Threaded
Binary Trees

19
Terminology
• Tree is a non – linear data structure which organizes data in a
hierarchical structure.
• In tree data structure, every individual element is called as a Node.
• Node in a tree, stores the actual data of that particular element and
link to next element in hierarchical structure.
• Binary tree – A binary tree is a tree which is a collection of zero or
more nodes and finite set of directed lines called branches that
connect the nodes.
21
Tree terminologies
Terminology
• A tree T can be empty or T contains a distinguished node
R called root of T and remaining nodes of T form an
ordered pair of disjoint binary trees T1 and T2.
• Suppose T is non empty and contains two sub trees
namely T1 and T2. If T1 and T2 are non empty , then T1 is
called left successor of R and T2 is called Right successor
of R.
• Root – If tree is not empty, the first node is called root
node.
• Left subtree – It is a tree which is connected to the left of
root.
• Right subtree - It is a tree which is connected to the right
of root.
Terminology
• Complete binary tree - A strictly binary or complete binary tree in which
the number of nodes at any level i is 2i.
• Example shows a complete binary tree because number nodes at level 1
is 2 and at level 2 is 4.
 Terminology
• Almost complete binary tree - A tree of depth d is said
to be an almost complete binary tree if it satisfies
following two properties :
1. If the tree is complete up to the level d-1, then the total
number of nodes at the level d-1 should be 2*(d-1)
2. The total number of nodes at level d may be equal to 2d. If
the total number of nodes at level d is less than 2d, then the
number of nodes at level d-1 should be 2(d-1) and in level d
the nodes should be present only from left to right.
Example: The tree is almost complete, because at level 1,
number of nodes are 2. At level 2, number of nodes is less than
4 but nodes are filled from left to right.
 Terminology
• Binary search tree –
• The left subtree of a node contains only nodes with keys lesser
than the node’s key.
• The right subtree of a node contains only nodes with keys greater
than the node’s key.
• The left and right subtree each must also be a binary search tree.
• A binary search tree is a binary tree in which for
each node say x in the tree, elements in the left sub-
tree are less than INFO(x) and elements in the right
sub-tree are greater than or equal to INFO(x). Every
node in the tree should satisfy this condition, if left
sub-tree or right sub-tree exists.
• Example: The given tree is Binary search tree
because at root the info field is 7. It left sub tree has
info field lesser and right subtree has higher value i.e
2 <7 and 9>7
Terminology

• Skewed trees are special kind

of trees in which the root
node will have either left
child nodes(left skewed tree)
or right child nodes only
(right skewed tree)
Parent and Child

• Parent: In a tree data structure, the node which is predecessor

of any node is called as parent node.
• Parent node can also be defined as "The node which has child
or children".
• Example: The tree has three parent nodes: A,B and C. A is parent of B
and VC. B is parent of D ,E. C is parent of F ,G.
• Child: In a tree data structure, the node which is descendant of
any node is called as child node. In simple words, the node
which has a link from its parent node is called as child node.
• Example: In the given tree, D and E are children nodes of B. In other
words, B is parent of D and E. Similarly F and G are children of C. (or C is
Parent of F and G)
 Sibling and Ancestor
• Siblings: In a tree data structure, nodes which belong
to same Parent are called as siblings.
• Example :In the given tree, D and E are siblings.
• The ancestors of a node are all the nodes in the tree
along the path of the root to that node.
• Example : In the given tree ancestor of D are: B and A,
ancestor of F are: C and A. Ancestor of B is A.
 Leaf , external and Internal Nodes
• Leaf: In a tree data structure, the node which does not
have a child is called as leaf node.
• Example For the given tree, nodes D, E ,F and G are leaf
nodes because they have no child. These are also called
External Nodes/ Terminal nodes .
• Internal nodes: In a tree data structure, the node which
has at least one child is called as internal node. The root
node is also said to be Internal Node
• Internal nodes are also called as 'Non-Terminal' nodes.
• Example: For the given tree, A B and C are internal nodes.
Edge
• Edge: In a tree data structure, the 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.
• Example: For the given tree, number of edges 5.
These are: A-B, A-C, B-D,B-E, C-F,C-G
 Degree
• Degree of a node: In a tree data structure, the
total number of children for a node(subtree of a
node) is called as degree of the Node.
• Example: For the given tree, Degree of B is 2 because
node B has two children.
• Degree of a Tree: The highest degree of a node
among all the nodes in a tree is as 'Degree of
Tree'
• Example: For the given tree, Degree of B,C,A is 2 and
degree of D,E,F,G is 0. So degree of the tree is 2.
Highest degree is 2, degree of the tree is 2
 Level ,Depth and Height
• Level: In a tree data structure, each step from top to bottom is called as a
Level. The root node is said to be at Level 0 and the children of root node are
at Level 1 and the children of the nodes which are at Level 1 will be at Level 2
and so on... The Level count starts with '0' and incremented by one at each
level (Step).
• Example : The given tree has two levels.
• 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.
• For the given tree, Height of the tree is 2.
• Longest path from leaf node to root node is 2.
• Depth: Total number of edges from root node to a particular node is called
as depth of that node. Depth of a tree is the total number of edges from root
node to a leaf node in the longest path. Depth of the root node = 0
• The terms “level” and “depth” are used interchangeably.
Path

• Path: In a tree data structure, the sequence of

Nodes and Edges from one node to another
node is called as path between those two
Nodes. Length of a Path is total number of
nodes in that path.
• Example : for the given tree, the path A - B - D has
length 3
 Subtree and forest
• Sub Tree: In a tree data structure, each
child from a node forms a sub tree
recursively. Every child node will form a
sub tree on its parent node.
• A forest is a set of disjoint trees
 Properties of Binary trees
• A tree is specially designated node called the toot. The remaining
nodes are partition into n>=0 disjoint sets T1,T2,T3.., where each of
these sets is a tree T1,T1,, are called sub trees of the root.
• Lemma 1
• In a k-ary tree where every node has either 0 or k children, the following
property is always true: (k is degree; total number of children of a node) L=
(k - 1)*I + 1 Where L = Number of leaf nodes
• I = Number of internal nodes

• Binary tree with 3 nodes (n=3, k=2)

ADT

37
Example for binary tree

38
• a Skewed binary tree
• b complete binary tree

39
40
Maximum number of nodes on level 3=23-1 =4
Maximum number of nodes on level of depth 3= 3=23-1 =7
41
n0=4+1
Degree 2 nodes: A,B,C,D
Leaf Nodes: H I E F G

42
Proof
• Let n be the number of nodes i.e sum of nodes with degree 0,1,2
• n=no+n1+n2 (eqn 1)
• Also number node n is also equal to number of branches B+1
• n=B+1 Where B=n1+2n2
• n=1+n1+2n2 (eqn 2)

• Subtract 2-1
• 0=1-n0+n2
• n0=1+n2

43
Terminology
• Complete binary tree - A strictly binary or complete binary tree in which
the number of nodes at any level i is 2i.
• Example shows a complete binary tree because number nodes at level 1
is 2 and at level 2 is 4.
45
Binary tree representation
• Different methods to represent a binary tree in memory.
• i) Array representation
• Ii) Linked list representation
• iii) Left child Right sibling representation
 1) Array representation
• 1-D array is used to represent a tree. Array is filled from
level 0 to last level
• This representation turns out to be inefficient for a binary search
tree representation
Array representation of Binary tree

48
 2) Linked list Representation.
• This representation uses double linked list
structure with three nodes namely INFO,RIGHT
and LEFT. This minimizes the wastage of memory.
• C structure representation
struct tree{
int data;
struct tree *left , * right;
};
typedef struct tree NODE;
50
Left child right sibling representation

51
Binary Tree Traversals

52
Binary tree traversals
• There are 6 possible ways of traversals
• Traversals is the process of visiting all nodes exactly once.
• LRV
• LVR
• VLR
• VRL
• RLV
• RVL
• Here only three traversals are discussed :
• Root Left Right
• Left Root Right
• Left Right Root

53
Expression tree

54
Binary Tree Traversals

• There are 3 standard ways of traversing mechanism in a binary tree T

with Root R.
1)Pre-Order
2) Post Order
3) Pre Oder
 Pre-order Traversing
i) Process root
ii) Traverse the left subtree of R
iii) Traverse the right subtree of R
• In this traversing, first root node is visited then left of it
then right of it is visited
void preorder(node *temp) {
if(temp!=NULL) {
printf(“%d”,temp->data);
preorder(temp->left);
preorder (temp->right);
}
}
Example: In Preorder tree traversal the result is: A, B, D, E, C, F, G
 Call of post order Value of root Action

1 + Print +

Trace of Pre- order

2 * Print *
3 * Print *
4 / Print /
5 A Print A
6 NULL
7 NULL
8 B Print B
9 NULL
10 NULL
11 C Print C
+**/ABCDE
12 NULL
13 NULL
14 D Print D
15 NULL
16 NULL
17 E Print E

57
 In-Order Traversing

1. Traverse the left subtree of R

2. Process root
3. Traverse the right subtree of R
void inorder(node *temp) {
if(temp!=NULL) {
inorder(temp->left);
printf(“%d”,temp->data);
inorder(temp->right);
}
}
Example: In In order tree traversal the result is: D, B, E, A, F, C, G
Trace of Inorder

A/B*C*D+E

59
 Post-Order Traversing
i) Traverse the left subtree of R
ii) Traverse the right subtree of R
iii) Process root
• In this traversing mechanism, first left node of root is processed then then right of root
is visited and then root node is visited
void postorder(node *temp) {
if(temp!=NULL) {
postorder(temp->left);
postorder (temp->right);
printf(“%d”,temp->data);
}
}
• Example: In postorder tree traversal the result is : D, E, B, F, G, C, A
 Call of post order Value of root Action Call of post order Value of root Action

1 + 23 * Print *

Trace of Post order

2 * 24 E
3 * 25 NULL
4 / 26 NULL
5 A 27 E Print E
6 NULL 28 + Print +
7 NULL
8 A Print A
9 B
10 NULL
11 NULL
AB/C*D*E+
12 B Print B
13 / Print /
14 C
15 NULL
16 NULL
17 C Print C
18 * Print *
19 D
20 NULL
21 NULL
22 D Print D
61
Exercise (Solved)
• Give Pre,post and Inorder traversal for the given tree
• In Order traversal :DGBAHEICF
• Post order traversal: GDBHIEFCA
• Pre order traversal: ABDGCEHIF
In Order traversal :DGBAHEICF
Post order traversal: GDBHIEFCA
Action Parent Left of parent Right of parent
A
(postorder) (postorder)
Find root/parent in A GDB HIEFC
postorder
GDB HIEFC

63
In Order traversal :DGBAHEICF
Post order traversal: GDBHIEFCA
Action Parent Left of parent Right of parent A
(postorder) (postorder)
Find root/parent in A GDB HIEFC
postorder B HIEFC
Find parent in GDB B GD --

GD

64
In Order traversal :DGBAHEICF
Post order traversal: GDBHIEFCA
Action Parent Left of parent Right of parent
A
(postorder) (postorder)
Find root/parent in A GDB HIEFC
postorder
B HIEFC
Find parent in GDB B GD --
Find parent in DG D -- D

65
In Order traversal :DGBAHEICF
Post order traversal: GDBHIEFCA
Action Parent Left of parent Right of parent
A
Find root/parent in A GDB HIEFC
postorder
Find parent in GDB B GD -- B HIEFC
Find parent in GD D -- D

66
In Order traversal :DGBAHEICF
Post order traversal: GDBHIEFCA
Action Parent Left of parent Right of parent
A
Find root/parent in A GDB HIEFC
postorder
Find parent in GDB B GD -- B C
Find parent in GD D -- D
Find parent in HIEFC C HIE F
HIE
D F

67
In Order traversal :DGBAHEICF
Post order traversal: GDBHIEFCA
Action Parent Left of parent Right of parent A
Find root/parent in A GDB HIEFC
postorder
Find parent in GDB B GD -- B C
Find parent in GD D -- G
Find parent in HIEFC C HIE F E
Find parent in HIE E H I D F

H I
G

68
In Order traversal :DGBAHEICF
Post order traversal: GDBHIEFCA
A

B C
INORDER: DGBAHEICF
PREORDER: ABDGCEHIF D
E
F
POST ORDER: GDBHIEFCA
H I
G

69
 INORDER (L V R A

B C
1
E
D F

H I
G

70
71
72
Construct expression tree:
(a+[b-c])*([d-e]/(f+g)-h)

73
74
75
Postorder

-9 13 34 18 12

76
 Pre order
Call to pre order Print Action
Node 12 Call Preorder(12)
Node -9 Call Preorder(-9)
NULL Call Preorder(Left of-9)
NULL Call Preorder(Right of-9)
Print -9 -9
Node 18 Call Preorder(18)
Node 13 Call Preorder(13)
NULL Call Preorder(Left 13)
NULL Call Preorder(right 13)
Print 13 13
Node 34 Call Preorder(34)
NULL Call Preorder(Left of 34)
-9 13 34 18 12
NULL Call Preorder(Right of 34)
Print 34 34
Print 18 18
Print 12 12 77
Inorder
Call to pre order Print Action
12 Call Inorder(12)
-9 Call Inorder(-9)
NULL Call Inorder(Left of -9)
Print -9 -9
NULL Call Inorder(right of -9)
Print 12 12
18 Call Inorder(18)
13 Call Inorder(13)
NULL Call Inorder(left of 13)
Print 13 13
NULL Call Inorder(Right of 13)
Print 18 18
34 Call Inorder(34) -9 12 13 18 34
NULL Call Inorder(left of 34)
Print 34 34
78
NULL Call Inorder(Right of 34)
 Threaded binary trees
• The idea of threaded binary trees is to make in order traversal faster
and do it without stack and without recursion. A binary tree is made
threaded by making all child pointers that would normally be NULL
point to the in-order successor/predessor of the node (if it exists).
• The number of null links can be reduced using threads.

INORDER: HDIBEAFCG
 Traversal in Threaded Binary Tree
• If ptr leftchild is NULL, replace ptrleftchild with a pointer to the node that
would be visited before ptr in an inorder traversal.
• (In-order- pre-deccssor)
• If ptrrightchild is null, replace ptrrightchild with a pointer to the node that
would be visited after ptr in an in-order traversal
• (In-order- successor)
• In-order traversal for the given binary tree: H D I B E A F C G
• Threaded binary tree is shown by connecting NULL right-child to In-order
successor and left NULL child to inorder predecessor

In this threaded binary tree, there are two dangling pointer

 Final threaded binary tree

In this threaded binary tree, there are two dangling pointer, this can
be corrected by connecting to a special node called Header node.
Modified Structure definition for threaded binary tree
leftThread and rightThread is set to
struct threadedTree{ 0 =0 if there is a thread, 1- for child node link
short int leftThread;
threadedTree * leftChild;
char data;
threadedTree * rightChild;
short int rightThread;
};
typedef struct threadedTree NODE;
83