Data Structures

Dr. Santhosh Kumar G

Associate Professor
Department of Computer Science and Engineering(Data Science)
Dayananda Sagar University, Harohalli, Karnataka.
# Modules and Course Content Hours
Introduction: Introduction to Data Structure, Classification, C Structure and Union, Array Definition,
1 Representation, Operations (Insertion, Deletion, Search and Traversal), Two/Multidimensional Arrays, 8
sparse matrix, C Pointers
INTRODUCTION TO ADT:
Stack: Definition, Array Representation of Stack, Operations on Stacks. Applications of Stack: Expression
2 evaluation, Conversion of Infix to Postfix, Infix to Prefix Recursion, Tower of Hanoi. 8
Queue: Definition, Representation of Queues, Operations of Queues, Circular Queue.
Applications of Queue: Job Scheduling, A Maze Problem.
Linked List: Types, Representation of Linked Lists in Memory. Traversing, Searching, Insertion, Deletion.
3 Circular List, Doubly Linked List, Operations on Doubly Linked List (Insertion, Deletion, Traversal). 8
Applications: Stack & Queue Implementation using Linked Lists. Case Study: Josephus problem.

Trees: Basic Terminology, Binary Trees and their representation,

Complete Binary Trees, Binary Search Trees, Threaded Binary Trees,
4 Operations on Binary Trees (Insertion, Deletion, Search & Traversal). 8
Applications: Expression Evaluation,
Case Study: Game Tree.
Efficient Binary Search Trees: Optimal Binary Search Trees, AVL Trees, Red Black Trees, Splay Trees.
5 Case Study: B Trees 7

Slides prepared by: Dr. Meenakshi Malhotra, Associate Professor, Department of CSE, Dayananda Sagar University, Harohalli, Karnataka. 2
Textbooks and Reference Books
1. A.M. Tannenbaum, Y Langsam, M J Augentien “Data Structures using C”, 1st
Edition, Pearson, 2019.
2. Ellis Horowitz, Susan Anderson-Freed, and Sartaj Sahni, “Fundamentals of Data
structures in C”, 2nd Edition, Orient Longman, 2008.

1. Brian. W. Kernighan, Dennis. M. Ritchie, “The C Programming Language”, 2nd

Edition, Prentice-Hall, 1988.
2. Gilbert & Forouzan, “Data Structures: A Pseudo-code approach with C”, 2nd
Edition, Cengage Learning,2014.

3
 Module 4
INTRODUCTION TO ADT:

Basic Terminology, Binary Trees and their

representation • INTRODUCTION TO ADT:
Complete Binary Trees • Trees: Basic Terminology, Binary Trees and
their representation, Complete Binary Trees,
Operations on Binary Trees (Insertion, Deletion,
Binary Search Trees, Threaded Binary Trees,
Search & Traversal).
Operations on Binary Trees (Insertion,
Binary Search Trees Deletion, Search & Traversal).
Threaded Binary Trees • Applications: Expression Evaluation,
• Case Study: Game Tree
Applications: Expression Evaluation,

Case Study: Game Tree

4
Coding competition
[Link]
[Link]
[Link]
[Link]

5
Trees
Introduction to Tree terminology

• A tree is an abstract model of a hierarchical structure that consists of nodes with a parent-child
relationship.
• for example, records, family trees and table of contents.
Introduction to Tree terminology

A tree is a finite set of one or more nodes such that:

(1) There is a specially designated node called the root.
(2) The remaining nodes are partitioned into n >= 0 disjoint sets T1, • • • Tn, where
each of these sets is a tree.
 T1, • • • Tn are called the subtrees of the root.
Introduction to Tree terminology
Node / Vertex
A Root

B C
Left subtree
Right subtree
D E F G

Edges H I Leaves

J K L M N
 What is a Tree?
Tree is a non-linear data structure which organizes data in a hierarchical structure

• Tree is a sequence of nodes

• There is a starting node known as a root node

• Every node other than the root has a parent node.
• Nodes may have any number of children
What is a Tree?
• A tree is a connected graph without any circuits.
• If in a graph, there is one and only one path between every pair of vertices,
then graph is called as a tree.
What is a Tree?
Tree-Basic Terminology
1) Root − Node at the top of the tree is called root.

• Every tree must have a root node.

Tree-Basic Terminology
2) 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.
Tree-Basic Terminology

3) Parent − In a tree data structure, the node which is a

predecessor of any node is called as PARENT NODE.

• The node which has a branch from it to any other node

is called a parent node.

• Parent node can also be defined as "The node which

has child / children".
Tree-Basic Terminology

4) Child − the node which is descendant of any node is

called as CHILD Node.

• The node which has a link from its parent 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.
Tree-Basic Terminology
5) Sibling − nodes which belong to same Parent are called as SIBLINGS.

• The nodes with the same parent are called Sibling nodes.
Tree-Basic Terminology

6) Leaf − the node which does not have a child is

called as LEAF Node.

• A leaf is a node with no child.

• The leaf nodes are also called as External Nodes.
• In a tree, leaf node is also called as 'Terminal' node.
 Tree-Basic Terminology
7) Internal nodes − the node which has atleast one
child is called as INTERNAL Node.

• Internal nodes are also called as 'Non-Terminal'

nodes.
 Tree-Basic Terminology
8) Degree− the total number of children of a node is
called as DEGREE of that Node.

• Degree of a node is total number of children it has.

• The highest degree of a node among all the nodes in a
tree is called as 'Degree of Tree'
 Tree-Basic Terminology
9) Level−
• in a tree each step from top to bottom is called
as a Level and
• the Level count starts with '0' and incremented
by one at each level (Step).

 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...
 Tree-Basic Terminology
10) Height −
• The total number of edges from leaf node to a particular
node in the longest path is called as HEIGHT of that
Node.

• Height of the root node is said to be height of the tree.

• Height of all leaf nodes is '0'.

 Tree-Basic Terminology
11) Depth − the total number of edges from root node
to a particular node is called as DEPTH of that Node.

 The total number of edges from the root node to a

leaf node in the longest path is said to be the Depth
of the tree.
 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'.
 Tree-Basic Terminology
12) Path −
• the sequence of Nodes and Edges from one node to
another node is called as PATH between that two
Nodes.

• Length of a Path is total number of nodes in that path.

• The path A - B - E - J has length 4.

 Tree-Basic Terminology
13) Subtree − each child from a node forms a
subtree recursively.

• Every child node will form a subtree on its

parent node.

14) Forest: It is a collection of disjoint trees.

From a given tree if we remove its root then we
get a forest.
Tree-Basic Terminology

Root Node: A
Parent of C and D: A
D is sibling of : B and C
Leaf Nodes: E, F, G, D
Internal Nodes: BCD
Depth of F: 2
Depth of Tree: 2
Depth of Root Node: 0
Height of Tree: 2
Height of A: 2
Height of G: 0
Degree of Node A: 3
Degree of Tree: 3
Degree of C 1
Characteristics of Trees
• Non-linear data structure
• Combines advantages of an ordered array
• Searching as fast as in an ordered array
• Insertion and deletion as fast as in the linked list
Application of Trees
• Directory structure of a file store
• Structure of arithmetic expressions
• Used in almost every 3D video game to determine what objects need
to be rendered.
• Used in almost every high-bandwidth router for storing router-tables.
• used in compression algorithms, such as those used by the .jpeg
and .mp3 file- formats.
Representation Of Trees
Left Child-Right Sibling Representation

I Left child-right sibling node structure

List Representation

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

Introduction to Binary Trees
• Binary tree is a special tree data structure in which each node can have at most 2
children.
• Each node has either 0 child or 1 child or 2 children.
Binary Trees
• A binary tree, T, is either empty or such that
i. T has a special node called the root node
ii. T has two sets of nodes LT and RT, called the left subtree and right subtree
of T, respectively.
iii. LT and RT are binary trees.
Binary Trees

(a) Skewed and (b) complete binary trees

Properties of Binary Trees
1) The maximum number of nodes
i. at level ‘i’ of a binary tree is 2i-1
For e.g.: Maximum number of nodes at level-1 (root node) in a binary
tree:
= 2i-1= 21-1=20=1
Thus, in a binary tree, maximum number of nodes that can be present at level-1 = 1.

ii. at depth k of a binary tree is 2k - 1, k > 1.

Properties of Binary Trees
2) Maximum number of nodes in a binary tree of height H =2H+1– 1

For e.g.: Maximum number of nodes in a binary tree of height 3

= 23+1 – 1= 16-1=15 nodes

Properties of Binary Trees
3) Minimum number of nodes in a binary tree of height H = H + 1
For e.g.: To construct a binary tree of height = 4, we need at
least 4 + 1 = 5 nodes.
Representation of Binary Trees
1) Array Representation

2) Linked List Representation

Binary Tree – Array Representation
• Number the nodes using the numbering scheme for a full binary tree.
• The node that is numbered i is stored in tree[i].
• if any node is stored at K position then the left child of a node is stored at index 2k and the right child is
stored at index 2K + 1 and the parent of a node is stored at floor(K/2) index.
Binary Tree – Array Representation
• Advantage: Direct access to any node is possible

• Disadvantage: In case of skewed trees, array is not fully utilized leading to wastage of
memory space
Binary Tree – Array Representation
int main() { int set_right(char key, int parent) {
root('A'); if (tree[parent] == '\0')
printf("\nCan't set child at %d , no parent
set_left('B',0);
found",(parent * 2) + 2);
set_right('C', 0); else{
set_left('D', 1); int print_tree() { tree[(parent * 2) + 2] = key;
set_right('E', 1); printf("\n"); printf("right tree done: %c", tree[(parent *
set_right('F', 2); for (int i = 0; 2)i <+ 2]
10;);i++) {
print_tree(); }
if (tree[i] != '\0')
return 0; return 0;
printf("%c",} tree[i]);
} else
printf( "-");
OUTPUT
int set_left(char key, int parent) {
#include <stdio.h>
} if (tree[parent] == '\0')
char tree[10]; return 0; ABCDE-F---
printf("\nCan't set child at %d , no parent
int root(char key) { } A B C D E * F2) + 1);
found",(parent
if (tree[0] != '\0') else{
printf("\nTree already had
root"); tree[(parent * 2) + 1] = key;
else { printf("left tree done: %c", tree[(parent * 2) +
tree[0] = key; 1] );
printf("tree created"); }
} return 0;
return 0; }
}
Binary Tree – Linked List Representation
• Use a linked list to represent a binary tree.
• Every node consists of three fields.
• left child address,
• actual data
• right child address. struct node
• Advantages: {
int data;
• No wastage of space struct node *left;
• Insertions and deletions are easier struct node *right;
• Disadvantages: };
• Does not provide direct access
• Needs additional space for storing left and right subtrees
Binary Tree – Linked List Representation
Binary Tree – Linked List Representation
Binary Tree – Linked List Representation
#include <stdio.h> // Create a new Node
#include <stdlib.h> struct node* create(int value) {
struct node* newNode = malloc(sizeof(struct node));
struct node { newNode->item = value;
int item; newNode->left = NULL;
struct node* left; newNode->right = NULL;
struct node* right; return newNode;
}; }

int main() { // Insert on the left of the node

struct node* root = create(1); struct node* insertLeft(struct node* root, int
insertLeft(root, 4); value) {
insertRight(root, 6); root->left = create(value);
insertLeft(root->left, 42); return root->left;
insertRight(root->left, 3); }
insertLeft(root->right, 2);
insertRight(root->right, 33); // Insert on the right of the node
} struct node* insertRight(struct node* root, int
value) {
root->right = create(value);
return root->right;
}
Binary Tree Traversals
• Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
• There are three types of binary tree traversals.
In - Order Traversal

Pre - Order Traversal

Post - Order Traversal

1. In-order Traversal (follows LDR)
 The left subtree is visited first, then the root, and later the right subtree.

void inorderTraversal(struct node* root) {

if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d ", root->item);
inorderTraversal(root->right);
}
2. Pre-order Traversal (follows DLR)
• The root node is visited first, then the left subtree and finally the right subtree.

// Preorder traversal
void preorderTraversal(struct node* root) {
if (root == NULL)
return;
printf("%d ", root->item);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
3. Post-order Traversal (follows LRD)
• The left subtree is visited first, then the right subtree and finally the root node.

// Postorder traversal
void postorderTraversal(struct node*
root) {
if (root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->item);
}
Binary Tree – Linked List Representation
int main() { struct node *tmp;
struct node* root = create(1); tmp = search(root, 6);
insertLeft(root, 4); if (tmp)
insertRight(root, 6); {
insertLeft(root->left, 42); printf("\nSearched node=%d in the tree\n", tmp-
insertRight(root->left, 3); >item);
insertLeft(root->right, 2); }
insertRight(root->right, 33); else
{
printf("Traversal of the inserted binary tree \ printf("%d Not found in tree.\n“,6);
n"); }
printf("Inorder traversal \n"); tmp = search(root, 99);
inorderTraversal(root); if (tmp)
{
printf("\nPreorder traversal \n"); printf("\nSearched node=%d in the tree\n", tmp-
preorderTraversal(root); >item);
}
else
printf("\nPostorder traversal \n"); {
printf("%d Not found in tree.\n", 99);
postorderTraversal(root); }
printf("\nheight of the tree: %d\n",
}
height(root));
Binary Tree – Linked List Representation
int height(struct node* node) struct node* search(struct node * tree, int
{ val)
if (node == NULL) {
if(!(tree))
return 0;
{
else { return NULL;
}
// Compute the height of each
subtree if(val == tree->item)
int lheight = height(node->left); {
int rheight = height(node->right); return tree;
// Use the larger one
}
if (lheight > rheight)
else if(search(tree->left, val)==NULL)
return (lheight + 1); {
else search(tree->right, val);
return (rheight + 1); }
} }
}
Binary Tree Traversals
Binary Tree Traversals
Binary Tree Traversals
Inorder Traversal

Preorder Traversal

Postorder Traversal

Level order Traversal

Application - Evaluate a Binary Expression Tree
• A binary expression tree is a binary tree where operators are stored in the tree’s
internal nodes and the leaves contain constants.
Find the output

110
100
Rules
Types of Binary Trees

• Full Binary Tree

• Complete Binary Tree

• Perfect Binary Tree

• Degenerate Binary Tree

• Balanced Binary Tree

1. Full / Proper / Strict Binary Tree
• If each node must contain either 0 or 2 children.
• Tree in which each node must contain 2 children except the leaf nodes.

Full Binary Tree Not a Full Binary Tree

Properties - Full / Proper / Strict Binary
Tree
• The number of leaf nodes is equal to the number of internal nodes plus 1.
2. Complete Binary Tree
• All the tree levels are filled entirely with nodes, except the lowest level of the
tree.
• In the last level, all the nodes must be as left as possible.
• In a complete binary tree, the nodes should be added from the left.
• In the last or the lowest level of this binary tree, every node should possibly reside
on the left side.
3. Perfect Binary Tree
• All interior nodes have two children and all leaves have the same depth or same
level
• A perfect binary tree of height h has 2h – 1 number internal nodes.
4. Degenerate / Pathological Binary Tree
• A degenerate or pathological tree is a tree having a single child either left or right.
• every parent node has only one child node.
5. Balanced Binary Tree
• Binary tree in which height of the left and the right sub-trees of every node may
differ by at most 1.
5. Balanced Binary Tree
• AVL (Adelson, Velski and Landis)- AVL Tree can be defined as height balanced binary
search tree in which each node is associated with a balance factor which is calculated by
subtracting the height of its right sub-tree from that of its left sub-tree.
• Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise,
the tree will be unbalanced and need to be balanced.
5. Balanced Binary Tree

• AVL Tree
6. Extended Binary Tree
• The full binary tree obtained by adding dummy nodes to a binary tree is called as
Extended Binary Tree.
• A binary tree can be converted into Full Binary tree by adding dummy nodes to
existing nodes wherever required.
Binary Tree – Linked List Representation
#include<stdio.h>

typedef struct node void preorder(node *t) //address of root node is passed in t
{ {
int data; if(t!=NULL)
struct node *left; {
struct node *right; printf("\n%d",t->data); //visit the root
} node; preorder(t->left); //preorder traversal on left subtree
preorder(t->right); //preorder traversal om right subtree
node *create() }
{ }
node *p;
int x; int main()
printf("Enter data(-1 for no data):"); {
scanf("%d",&x); node *root;
if(x==-1) root=create();
return NULL; printf("\nThe preorder traversal of tree is:\n");
p=(node*)malloc(sizeof(node)); preorder(root);
p->data=x; return 0;
printf("Enter left child of %d:\n",x); }
p->left=create();

printf("Enter right child of %d:\n",x);

p->right=create();
return p;
}
Binary Search Tree (BST)
 Binary Search tree can be defined as a class of binary trees, in
which the nodes are arranged in a specific order. This is also
called ordered binary tree.

 It may be empty. If it is not empty, it satisfies the following

properties:
 Every element has a key, and no two elements have the
same key, that is, the keys are unique.
 In a BST, the value of all the nodes in the left sub-tree is less
than the value of the root.
 Similarly, the value of all the nodes in the right sub-tree is
greater than or equal to the value of the root.
 The left and right subtrees are also binary search trees. This
rule will be recursively applied to all the left and right sub-
trees of the root.
Binary Search Tree (BST)
 Binary Search tree can be defined as a class of binary trees, in
which the nodes are arranged in a specific order. This is also
called ordered binary tree.

 It may be empty. If it is not empty, it satisfies the following

properties:
 Every element has a key, and no two elements have the
same key, that is, the keys are unique.
 In a BST, the value of all the nodes in the left sub-tree is less
than the value of the root.
 Similarly, the value of all the nodes in the right sub-tree is
greater than or equal to the value of the root.
 The left and right subtrees are also binary search trees. This
rule will be recursively applied to all the left and right sub-
trees of the root.
Advantages of using binary search tree
• Searching becomes very efficient in a binary search tree since, we get a hint at each
step, about which sub-tree contains the desired element.

• The binary search tree is considered as efficient data structure compared to arrays and
linked lists. In the searching process, it removes half sub-tree at every step.

• It also speeds up the insertion and deletion operations compared to that in array and
linked list.
Operations on BST
• Insertion
• Search
• Deletion
• Traversal
BST Insertion
• Insert values 43, 10, 79, 90, 12, 54, 11, 9, 50 into a BST
BST Insertion
BST Operations
void create()
{
int data;
struct bstnode * temp;
printf("Enter data of node to be inserted : ");
scanf("%d", &data);
temp = (struct bstnode *)malloc(sizeof(struct
bstnode));
temp->value = data;
temp->l = temp->r = NULL;
}
tree—pointer search(tree—pointer root, int
key)
{
/*return a pointer to the node that contains
key. If there is no such node, return
NULL.*/
if (! root)
return NULL;
if (key == root->data)
return root;
if (key< root->data)
return search(root->left—child, key);
return search(root->right_child,key);
BST Operations
void insert—node(struct bstnode *node, int num)
/*If num is in the tree pointed at by node do nothing; otherwise add a
new node with data num * /
{
struct bstnode *temp = search(*node, num);
if (temp ==NULL)
{
/*num is not in the tree*/
struct bstnode *ptr= (struct bstnode*)malloc(sizeof(struct
bstnode));

ptr->data = num;
ptr->left—child =ptr->right—child = NULL;

if (*node) /insert as child of node*/

if (num <node->data)
node->left—child = ptr;
else
node->right—child = ptr;
else *node = ptr;
}
}
BST Deletion
BST Deletion
BST Deletion
BST Deletion
BST Deletion
void delete() void delete1(struct btnode *t) /* To delete node having right hand child */
{
{ int k;
else if (t->l == NULL)
int data; {
/* To delete leaf node */ if (t1 == t)
if (root == NULL) if ((t-> l == NULL) && (t-> r == NULL)) {
{ root = t->r;
{ if (t1-> l == t)
printf("No elements in a tree to delete"); t1 = root;
{
}
return; t1-> l = NULL;
} else if (t1->r == t)
}
else t1->r = t->r;
printf("Enter the data to be deleted : "); { else
scanf("%d", &data); t1->r = NULL; t1->l = t->r;
t1 = root; }
t == NULL;
t = NULL;
t2 = root; free(t); free(t);
search1(root, data); return; return;
} } }
void search1(struct btnode *t, int data) /* To delete node having one left hand child */
/* To delete node having two child */
{ else if ((t->r == NULL))
else if ((t->l != NULL) && (t->r != NULL))
{
if ((data>t->value)) {
if (t1 == t)
{ { t2 = root;
t1 = t; root = t->l; if (t->r != NULL)
search1(t->r, data); t1 = root; {
}
} else if (t1->l == t)
k = smallest(t->r);
else if ((data < t->value)) { flag = 1;
{ t1->l = t->l; }
t1 = t; else
} {
search1(t->l, data); else
} k =largest(t->l);
{
flag = 2;
else if ((data==t->value)) t1->r = t->l;
} }
{
t = NULL; search1(root, k);
delete1(t); free(t); t->value = k;
} return; }}
int smallest(struct btnode *t)
{
t2 = t;
if (t-> l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}

/* To find the largest element in the left sub tree */

int largest(struct btnode *t)
{
if (t-> r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}
Application - Evaluate a Binary Expression
Tree
• A binary expression tree is a binary tree where operators are stored in the tree’s
internal nodes and the leaves contain constants.
Find the output

110
100
Rules
Slides prepared by: Dr. Meenakshi Malhotra, Associate Professor, Department of CSE, Dayananda Sagar University, Harohalli, Karnataka. 89
Slides prepared by: Dr. Meenakshi Malhotra, Associate Professor, Department of CSE, Dayananda Sagar University, Harohalli, Karnataka. 90
Slides prepared by: Dr. Meenakshi Malhotra, Associate Professor, Department of CSE, Dayananda Sagar University, Harohalli, Karnataka. 91
Slides prepared by: Dr. Meenakshi Malhotra, Associate Professor, Department of CSE, Dayananda Sagar University, Harohalli, Karnataka. 92
Slides prepared by: Dr. Meenakshi Malhotra, Associate Professor, Department of CSE, Dayananda Sagar University, Harohalli, Karnataka. 93
Slides prepared by: Dr. Meenakshi Malhotra, Associate Professor, Department of CSE, Dayananda Sagar University, Harohalli, Karnataka. 94
2-Way THREADED BINARY TREES

An empty threaded Binary tree

typedef struct threaded_tree *k

threaded_pointer;

struct threaded_tree {
int left_thread;
threaded_pointer left_child;
char data;
threaded_pointer rightchiId;
int right_thread;
};
2-Way THREADED BINARY TREES

In two-way threaded Binary trees

 the right link field of a node containing

NULL values is replaced by a thread that
points to nodes inorder successor and
 left field of a node containing NULL values
is replaced by a thread that points to
nodes inorder predecessor
2-Way THREADED BINARY TREES

In the two-way threaded Binary tree, Notice that

no left thread is possible for the first node and no
right thread is possible for the last node.

 This is because they don't have any inorder

predecessor and successor respectively.
 This is indicated by threads pointing nowhere.

 So to maintain the uniformity of threads, we maintain a special node called the header node.
Inorder Traversal of a Threaded Binary Tree
Finding the inorder successor of a node
threaded_pointer insucc(threaded_pointer
tree)
{
/*find the inorder sucessor of tree in a threaded
binary tree */
threaded_pointer temp;
temp = tree->right_child; Inorder traversal of a threaded binary tree
if (!tree->right_thread)
void tinorder(threaded_pointer tree)
while (!temp->left_thread)
{
temp =temp->left_child;
/*traverse the threaded binary tree inorder
return temp; */
} threaded_pointer temp = tree;
for (;;) {
temp = insucc(temp);
if (temp == tree)
break;
printf("%3c", temp->data);
}
}
Inserting A Node Into A Threaded Binary Tree

To insert child as the right child of parent we must:

1) change parent -> right_thread to FALSE
2) set child -> left_thread and child -> right_thread to TRUE
3) set child -> left_child to point to parent
4) set child -> right_child to parent -> right_child
5) change parent -> right_child to point to child
Inserting A Node Into A Threaded Binary Tree

To insert child as the right child of parent

we must:
1) change parent -> right_thread to FALSE
2) set child -> left_thread and child ->
right_thread to TRUE
3) set child -> left_child to point to parent
4) set child -> right_child to parent ->
right_child
5) change parent -> right_child to point to
child
Inserting A Node Into A Threaded Binary Tree
void insert_right(threaded_pointer parent, threaded_pointer child)
{ /*insert child as the right child of parent in a threaded binary
tree */
threaded_pointer temp;
child->right_chiId = parent->right_child;
child->right_thread = parent->right_thread;
child—>left_child = parent;
child->left_thread = TRUE;
parent->right_child = child;
parent->right_thread = FALSE;
if (!child->right_thread)
{
temp = insucc(child);
temp->left_child = child;
}
}