CSE2PM01A Data Structures

S. Y. B. Tech CSE Semester – IV

SCHOOL OF COMPUTER ENGINEERING AND TECHNOLOGY

9/12/2024 2
 Tree
▪ Basic Terminology, Binary Tree- Properties
▪ Converting Tree to Binary Tree.
▪ Representation using Sequential and Linked organization .
▪ Binary tree creation and Traversals, Operations on binary tree.
▪ Binary Search Tree (BST) and its operations
▪ Threaded binary tree- Creation and Traversal of inorder Threaded Binary tree.
▪ Case Study- Expression tree.

9/12/2024 3
 Natural environment Tree
leaves

branches
root

9/12/2024 4
 Computer Scientist’s View
root

leaves

branches
nodes

9/12/2024 5
 Tree (example)
node

9/12/2024 6
 General tree

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

(i)There is a specially designated node called the root;

(ii) 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.

9/12/2024 7
 Sample Tree

Figure 8: Sample Tree

9/12/2024 8
 Tree Terminology

Root: Node without parent (A) Subtree: Tree consisting of a node and its
Siblings: Nodes share the same parent descendants
Ancestors of a node: all the nodes along the path from root to that node
A
Descendant of a node: child, grandchild, grand-grandchild, etc.
The height or depth of a tree is defined to be the maximum level of any
node in the tree.(4)
B C D
Degree of a node: the number of subtrees(children) of a node is called degree
Degree of a tree: the maximum of the degree of the nodes in the tree.
Nonterminal nodes: other nodes E F G H
leaf or terminal node: Node that have degree zero (E, I, J, K, G, H, D)
The level of a node is defined by initially letting the root be at level one. If a subtree
node is at level l, then its children are at level l + 1. I J K

9/12/2024 9
 Tree Properties

A Property Value
Number of nodes 9
B C Height 5
Root Node A
Leaves C,D,F,H,I
D E F
Interior nodes B,E,G
Ancestors of H A,B,E,G
Descendants of B D,E,G,H,I,F
G Siblings of E D,F
Right subtree of A A,C
H I Degree of this tree 3

9/12/2024 10
 Binary Tree

▪ Every node in a binary tree can have at most two children.

▪ A binary tree is a finite set of nodes that is either empty or consists of a

root and two disjoint binary trees called the left subtree and the right
subtree.

9/12/2024 11
 Structures that are not Binary tree
binary trees
A

B c

E F
D

I
G H

9/12/2024 12
 Maximum Number of Nodes in BT

● The maximum number of nodes on level i of a binary tree is 2i-1, i>=1.

● The maximum number of nodes in a binary tree of depth k is 2k-1, k>=1.

9/12/2024 13
 Binary Trees
▪ A Full binary tree of depth K is a binary tree of depth having 2k-1 nodes
k>=0

▪ Complete Binary Tree

A binary tree T with n levels is complete if all levels except possibly the
last are completely full, and the last level has all its nodes to the left side.

9/12/2024 14
 Complete Binary Trees - Example
A

B C

F G
D E

H I J K

9/12/2024 15
 A Full Binary Tree - Example

9/12/2024 16
 Complete Binary Trees

The second node of a complete

binary tree is always the left child
of the root...
... and the third node is always the
right child of the root.

9/12/2024 17
 Complete Binary Trees

The next nodes must

always fill the next level
from left to right.

9/12/2024 18
 Complete Binary Trees

The next nodes must

always fill the next
level from left to right.

9/12/2024 19
 Complete Binary Trees

The next nodes must

always fill the next
level from left to right.

9/12/2024 20
 Complete Binary Trees

The next nodes must

always fill the next
level from left to right.

9/12/2024 21
 Complete Binary Trees

The next nodes must

always fill the next
level from left to right.

9/12/2024 22
 Complete Binary Trees

The next nodes must

always fill the next
level from left to right.

9/12/2024 23
 Is This Complete?

9/12/2024 24
 Is This Complete?

9/12/2024 25
 Full BT VS Complete BT

A A

B C B C

D E F G D E F G

H I H I J K L M N O

Complete binary tree Full binary tree of depth 4

9/12/2024 26
 Samples of Trees

A A 1 A

B B 2 B C

C Skewed Binary
Tree 3 D E F G
D

4 H I
E 5
Complete Binary Tree
9/12/2024 27
 Converting tree to binary tree

▪ Any tree can be transformed into binary tree.

▪ by left child-right sibling representation

▪ The left subtree and the right subtree are distinguished.

9/12/2024 28
 Tree Representations

A A A

B B B

A A A

B C B C B

C
Left child-right sibling
Binary tree
9/12/2024 29
 Representation of Trees
▪ Left Child-Right Sibling Representation
▪ Each node has two links (or pointers).
▪ Each node only has one leftmost child and one closest sibling.

data A
left child right sibling

B C D

E F G I H J

K L M

9/12/2024 30
 Degree Two Tree Representation

E C

K F G D
Binary Tree!
L I

M H

J
9/12/2024 31
 Converting to a Binary Tree
A

B
▪Binary tree left child = leftmost child
C
▪Binary tree right child= right sibling
D
A
F E

B C D E
G H

I
F G H
J
I J
9/12/2024 32
 [1] A
Sequential Representation [2] B
[3] C
(1) waste space
[4] D
[1] A (2) insertion/deletion
A [5] E
[2] B problem
[6] F
[3] -- [7]
B G
[4] C [8]
A H
[5] -- [9]
C I
[6] --
[7] -- B C
D [8] D
[9] --
D
. . E F G
E
[16] E
H I
9/12/2024 33
 Node Number Properties
1

2 3

4 5 6 7
8 9 10 11 12 13 14 15

Parent of node i is node i/2

▪ But node 1 is the root and has no parent
Left child of node i is node 2i if 2i is <=n
▪ But if 2i > n, node i has no left child
Right child of node i is node 2i+1 if 2i+1 is <=n
▪ But if 2i+1 > n, node i has no right child
9/12/2024 34
 Linked Representation

Struct Node{
int data;
struct Node *lchild;
struct Node *rchild;
};
data

left_child data right_child

left_child right_child

9/12/2024 35
 Linked Representation Example
root a

b c

d e

g
f
leftChild
element h
rightChild
9/12/2024 36
 Binary Tree Creation

struct treenode int main()

{ {
char data[10];
struct treenode *left; allocate the memory for root and read data ;
struct treenode *right; Set Left and right of root node to NULL;
} create_r(root);
}

9/12/2024 37
Algorithm create_r(struct treenode* root) {
temp = root
Accept choice whether data is added to left of temp->data;
if ch=‘y’{
Allocate a memory for curr and accept data;
Set Left and right of curr node to NULL;
temp->left=curr;
create_r(curr);
}

Accept choice whether data is added to right of temp->data;

if ch=‘y’ {
Allocate a memory for curr and accept data;
Set Left and right of curr node to NULL;
temp->right=curr;
create_r(curr);
}
}
9/12/2024 38
Algorithm create_nr(struct treenode* root) else {
{ if ch='r’
do {
{ if temp->right=NULL
temp=root; {
flag=0; temp->right=curr;
allocate memory for curr and accept data; flag=1;
while(flag==0) }
{
temp=temp->right;
Accept choice to add node(left or right);
}
if ch='l’
} //else end
{
if temp->left=NULL }//while flag
{ temp->left=curr; Accept choice for continuation;
flag=1; } // do while end
} }// algo end
temp=temp->left;
}
9/12/2024 39
 Binary Tree Traversals

• Let L, V/D and R stand for moving left, visiting the node, and moving right.
• There are six possible combinations of traversal
– LVR, LRV, VLR, VRL, RVL, RLV
• Adopt convention that we traverse left before right, only 3 traversals remain
– LVR, LRV, VLR
– inorder, postorder, preorder

9/12/2024 40
 Binary Tree Traversals
▪A traversal is where each node in a tree is visited once

▪There are two very common traversals

▪ Breadth First
▪ Depth First

9/12/2024 41
 Breadth First
▪In a breadth first traversal all of the nodes on a given level are visited and then all
of the nodes on the next level are visited.

▪Usually in a left to right fashion

▪This is implemented with a queue

9/12/2024 42
 Depth First
▪In a depth first traversal all the nodes on a branch are visited before any others
are visited

▪There are three common depth first traversals

▪ Inorder
▪ Preorder
▪ Postorder

▪Each type has its use and specific application

9/12/2024 43
 Inorder Example (Visit = print)
a

b c
f
d e
g h i j

g d h b e i a f j c

9/12/2024 44
 Preorder Example (Visit = print)
a

b c
f
d e
g h i j

a b d g h e i c f j

9/12/2024 45
 Postorder Example (Visit = print)
a

b c
f
d e
g h i j

g h d i e b j f c a

9/12/2024 46
 Depth first traversal

pre-order (red): F, B, A, D, C, E, G, I, H;
in-order (yellow): A, B, C, D, E, F, G, H, I;
post-order (green): A, C, E, D, B, H, I, G, F.

9/12/2024 47
 Linked Representation (using typedef)

typedef struct TreeNode {

char data[10];
struct TreeNode *left_child;
struct TreeNode *right_child;
} TreeNode;

data

left_child data right_child

left_child right_child

9/12/2024 48
 Inorder Traversal (recursive version)

Algorithm inorder_r(Treenode *temp)

{
if temp!=NULL
{
inorder_r(temp->left);
Print temp->data;
inorder_r(temp->right);
}
} pre-order (red): F, B, A, D, C, E, G, I, H;
in-order (yellow): A, B, C, D, E, F, G, H, I;
post-order (green): A, C, E, D, B, H, I, G, F.

9/12/2024 49
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

9/12/2024 50
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 13 – do left
9/12/2024 51
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 9 – do left
At 13 – do left
9/12/2024 52
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 2 – do left
At 9 – do left
At 13 – do left
9/12/2024 53
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 2 – print
At 9 – do left
At 13 – do left
9/12/2024 54
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 2 – do right
At 9 – do left
At 13 – do left
9/12/2024 55
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 2 - done
At 9 – do left
At 13 – do left
9/12/2024 56
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 9 – Print
At 13 – do left
9/12/2024 57
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 9 – do right
At 13 – do left
9/12/2024 58
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 9 – done
At 13 – do left
9/12/2024 59
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 13 – print
9/12/2024 60
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 13 – do right
9/12/2024 61
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 42 – do left
At 13 – do right
9/12/2024 62
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 42 – print
At 13 – do right
9/12/2024 63
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 42 – do right
At 13 – do right
9/12/2024 64
 Use of the Activation Stack

With a recursive module, we can make use of 13

the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 42 – done
At 13 – do right
9/12/2024 65
 Use of the Activation Stack
With a recursive module, we can make use of 13
the activation stack to visit the sub-trees and
“remember” where we left off.
9 42

At 13 – done
9/12/2024 66
 Preorder Traversal (recursive version)

Algorithm preorder(Treenode * temp)

/* preorder tree traversal */
{
if (temp!=NULL) {
print(temp->data);
preorder(temp->left);
predorder(temp->right);
} pre-order (red): F, B, A, D, C, E, G, I, H;
} in-order (yellow): A, B, C, D, E, F, G, H, I;
post-order (green): A, C, E, D, B, H, I, G, F.

9/12/2024 67
 Postorder Traversal (recursive version)

Algorithm postorder(Treenode * temp)

/* postorder tree traversal */
{
if (temp!=NULL) {
postorder(temp->left);
postdorder(temp->right);
print(temp->data);
} pre-order (red): F, B, A, D, C, E, G, I, H;
} in-order (yellow): A, B, C, D, E, F, G, H, I;
post-order (green): A, C, E, D, B, H, I, G, F.

9/12/2024 68
 Stack for tree traversal
typedef struct TreeNode { void push(TreeNode* node) {
char data[10];
if (top == STACK_SIZE - 1) {
struct TreeNode *left;
struct TreeNode *right; printf("Stack overflow\n");
} TreeNode; return;
}
// Global stack variables
#define STACK_SIZE 100 stack[++top] = node;
TreeNode* stack[STACK_SIZE]; // Array to store stack }
elements TreeNode* pop() {
int top = -1; // Index of the top element
if (isStackEmpty()) {
// Function to check if the stack is empty printf("Stack underflow\n");
int isStackEmpty() { return NULL;
return top == -1; }
} TreenNode *node = stack[top--];
return node;
}
9/12/2024 69
 Nonrecursive Inorder Traversal

Algorithm inorder_nonrec(TreeNode* root) {

temp = root; //start traversing the binary tree at the root node
while(1) {
while(temp is not NULL)
{
push temp onto stack;
temp = temp ->left;
}
if stack empty
break;
pop stack into temp;
visit temp; //visit the node
temp = temp ->right; //move to the right child pre-order (red): F, B, A, D, C, E, G, I, H;
} //end while in-order (yellow): A, B, C, D, E, F, G, H, I;
} //end algorithm post-order (green): A, C, E, D, B, H, I, G, F.

9/12/2024 70
 Nonrecursive Preorder Traversal
Algorithm preorder_nonrec(TreeNode* root) {
temp = root; //start the traversal at the root node
while(1) {
while(temp is not NULL)
{
visit temp;
push temp onto stack;
temp = temp ->left;
}
if stack empty
break;
pop stack into temp;
temp = temp ->right; //visit the right subtree pre-order (red): F, B, A, D, C, E, G, I, H;
} //end while in-order (yellow): A, B, C, D, E, F, G, H, I;
} //end algorithm post-order (green): A, C, E, D, B, H, I, G, F.

9/12/2024 71
 Nonrecursive Postorder Traversal
while(stack not empty && stack top right is temp)
{
pop stack into temp;
Algorithm postorder_nonrec(TreeNode* root) visit temp
{ }
temp=root; if stack empty
while(1) break;
{ temp= stack[top]->right;
while(temp is not NULL) } // end while
{
push temp onto stack; } // end algorithm
temp = temp ->left;
}
if stack top right is NULL
{
pre-order (red): F, B, A, D, C, E, G, I, H;
pop stack into temp;
in-order (yellow): A, B, C, D, E, F, G, H, I;
visit temp;
post-order (green): A, C, E, D, B, H, I, G, F.
}

9/12/2024 72
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) a
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer

}
}

9/12/2024 73
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL)
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
a
}
}

9/12/2024 74
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) b c
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
a
}
}

9/12/2024 75
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) c
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
ab
}
}

9/12/2024 76
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) c d e
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
ab
}
}

9/12/2024 77
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) d e
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
abc
}
}

9/12/2024 78
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) d e f
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
abc
}
}

9/12/2024 79
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) e f
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
abcd
}
}

9/12/2024 80
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL) f
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
abcde
}
}

9/12/2024 81
Algorithm BFS(TreeNode *root)
{
temp=root;
a
Insert temp into queue;
while Queue not empty
b c
{

f
Remove from queue into temp; d e
visit temp; Queue
if(temp->left is not NULL)
insert temp->left into queue;
if(temp->right is not NULL)
insert temp->right into queue; Answer
abcdef
}
}

9/12/2024 82
 Assignment no 1
2. Implement binary tree and perform following operations: Creation of
binary tree and traversal recursive and non-recursive.

9/12/2024 83
 Operations on binary tree
Copying Binary Tree (recursive)
Copy of binary tree using non recursive is done through preorder
treenode *copy(TreeNode *root)
{
temp=NULL
if (root!=NULL) {

Allocate memory for temp

temp->data=root->data;
temp->left=copy(root->left);
temp->right=copy(root->right);
}
return temp;
}

9/12/2024 84
Algorithm copy_nr(TreeNode *root2)
{ //root2 is original tree push(temp1);
Allocate memory for root1
push(temp2);
temp1=root1;
temp2=root2; Move temp1 to temp1->left
copy(temp1->data,temp2->data); Move temp2 to temp2->left
while(1) }
{ if stack empty break;
while(temp2!=NULL) else
{
{
if(temp2->left!=NULL)
{ Pop to temp1
Allocate memory for temp1->left; Pop to temp2
copy (temp1->left->data,temp2->left->data); temp1=temp1->right;
} temp2=temp2->right;
if(temp2->right!=NULL)
}
{
Allocate memory for temp1->right;; } //end while
copy temp1->right->data,temp2->right->data); }
}

9/12/2024 85
 Erasing nodes in binary tree
Use postorder

9/12/2024 86
 int depth_r(TreeNode *root)
Algorithm depth_nr(TreeNode *root)
{
{
Initialize d to 0; Initialize t1=0,t2=0;
temp=root; if(root==NULL)
while(1) return 0;
{ else
while(temp!=NULL) {
{
t1=depth_r(root->left);
push temp;
t2=depth_r(root->right);
move temp to temp->left;
if(d<top) if(t1>t2)
d=top; } return ++t1;
if(stack top right is NULL) else
{ return ++t2;
pop to temp; } }
while(stack not empty && stack top right is temp)
}
{
pop to temp ; }
if stack empty
break;
move temp to stack top right;
}
cout<<"\nDepth is "<<d+1; }

9/12/2024 87
 Algorithm mirror_r(TreeNode *root) Algorithm mirror_nr(TreeNode *root)
{ {
swap left and right; temp=root;
if(root->left!=NULL)
insqueue(temp);
mirror_r(root->left);
if(root->right!=NULL) while(!qempty())
mirror_r(root->right); {
} temp=delqueue();
swap left and right;
if(temp->left!=NULL)
insqueue(temp->left);
if(temp->right!=NULL)
insqueue(temp->right);
}
dispbfs(root);
}

9/12/2024 88
 Binary search Trees

It is a binary [Link] may be [Link] it is not empty then it satisfies the following properties

⮚Every element has a unique key.

⮚The keys in a nonempty left subtree are smaller than the key in the root of subtree.
⮚The keys in a nonempty right subtree are larger than the key in the root of subtree.
⮚The left and right subtrees are also binary search trees.

◦ Binary search trees provide an excellent structure for searching a list and at the same time for
inserting and deleting data into the list.

9/12/2024 89
Binary Search Tree

All < K All > K

9/12/2024 90
(a), (b) - complete and balanced trees;
(d) – nearly complete and balanced tree;
(c), (e) – neither complete nor balanced trees

9/12/2024 91
9/12/2024 92
 Binary search Trees

typedef struct BST

{
char word[10];
char meaning[20];
struct BST *left;
struct BST *right;
}BST;

9/12/2024 93
Algorithm create()
{ else {
allocate memory and accept the data for root node; if(temp->right=NULL)
do {
{
temp->right=curr;
temp=root;
flag=1;
flag=0;
}
allocate memory and accept the data for curr node;
while(flag==0) else
{ move temp to temp->right;
if(curr->data < temp->data) } //end else
{ } //end while flag
if(temp->left=NULL) Accept choice for adding more nodes;
{
}while(choice =yes); //end do
temp->left=curr;
} //end algorithm
flag=1;
}
else
move temp to temp->left
} //end if compare

9/12/2024 94
binary search tree creation
Jyoti, Deepa, Rekha, Amit, Gilda, Anita, Abolee, Kaustubh, Teena, Kasturi, Saurabh

9/12/2024 95
 Algorithm search_r(BST *temp, char str[10])
Algorithm search (BST *root) {
{ Initialize f to 0;
Initialize flag = 0; if(temp != NULL)
Accept string to be searched ; {
flag = search_r(root, str); if(str = temp->data)
if(flag = 1) return 1;

print found; if(str < temp->data)

f = search_r(temp->left, str);
else
if(string > temp->data)
print not found;
f = search_r(temp->right, str);
}
}
return f;
}

9/12/2024 96
Algorithm search_nr(BST *root)
{
Initialize flag to 0;
temp = root;
Accept string to be searched;
while(flag = 0 && temp != NULL)
{
if(string = temp->data)
{
flag=1; break;
}
else if(string < temp->data)
move temp to temp->left;
else
move temp to temp->right;
} //end while
if(flag = 1)
Print found;
else
Print not found;
} //end algorithm

9/12/2024 97
 Function DeleteItem
First, find the item; then, delete it

Important: binary search tree property must be preserved!!

We need to consider following different cases:

(1) Deleting a leaf
(2) Deleting a node with only one child
(3) Deleting a node with two children
(4) Deleting the root node

9/12/2024 98
 (1) Deleting a leaf

9/12/2024 99
 Deletion - Leaf Case
Algorithm sets corresponding link of the parent to NULL and disposes the node

Delete(17) 10

5 15

2 9 20

7 17 30

9/12/2024 100
 (2) Deleting a node with only one child

It this case, node is cut from the tree and algorithm links single child (with it's subtree) directly to the parent
of the removed node.

9/12/2024 101
 Deletion - One Child Case
Delete(15) 10

5 15

2 9 20

7 30

9/12/2024 102
 (3) Deleting a node with two
children (contd…)

Find inorder successor

◦ Go to the right child and then move to the left till we get NULL for the leftmost node

◦ To the inorder’s successor ,attach the left of the node which we want to delete

9/12/2024 103
 if(curr==root) //deletion of root
{
if(curr->rightc==NULL)
root=root->leftc;
else if(curr->leftc==NULL)
root=root->rightc;
else if(curr->rightc!=NULL && curr->leftc!=NULL) 10
{
temp=curr->leftc;
root=curr->rightc; 5 15
s=curr->rightc;
while(s->leftc!=NULL)
{ 2 9 20
s=s->leftc;
}
s->leftc=temp;
7 17 30
}
}

9/12/2024 104
 else if(curr!=root) //deletion of node which is not root
{
if(curr left and right is NULL ) //deletion of a leaf
{
if(parent->leftc==curr) 10
parent->leftc=NULL;
else
parent->rightc=NULL; 5 15
}

2 9 20

7 17 30

9/12/2024 105
 else if(curr!=root) //deletion of node which is not root
{
if(curr left and right is NULL ) //deletion of a leaf
{
if(parent->leftc==curr)
parent->leftc=NULL;
else
parent->rightc=NULL;
}
else if(curr->leftc is NULL) //deletion of a single child 11
{
if(parent->leftc==curr)
parent->leftc=curr->rightc;
5 15
else
parent->rightc=curr->rightc; 2 9 20
}

10 17 30
9/12/2024 106
 else if(curr!=root) //deletion of node which is not root
{ else if(curr->rightc is NULL) //deletion of a
if(curr left and right is NULL ) //deletion of a leaf single child
{ {
if(parent->leftc==curr) if(parent->leftc==curr)
parent->leftc=NULL; parent->leftc=curr->leftc;
else else
parent->rightc=NULL;
parent->rightc=curr->leftc;
}
} 10
else if(curr->leftc is NULL) //deletion of a single child
{
if(parent->leftc==curr)
parent->leftc=curr->rightc;
5 15
else
parent->rightc=curr->rightc; 2 9 20
}

7 17 30
9/12/2024 107
 else //deletion of a node having two child
{
s=curr->rightc;
temp=curr->leftc;
while(s->leftc!=NULL)
{
s=s->leftc;
}
s->leftc=temp;
if(parent->leftc==curr)
10
parent->leftc=curr->rightc;
else 5 15
parent->rightc=curr->rightc;
}
} 2 9 20
Assign curr left and right to NULL;
free(curr);
} 7 17 30
9/12/2024 108
 Assignment
Implement dictionary using binary search tree where dictionary stores keywords & its meanings.
Perform following operations:
1. Insert a keyword
2. Delete a keyword
3. Create mirror image and display level wise
4. Copy

9/12/2024 109
 Threaded Binary Tree

In a linked representation of a binary tree, the number of null links (null pointers) are
actually more than non-null pointers.
Consider the following binary tree:

9/12/2024 110
 Threaded Binary Trees

Two many null pointers in current representation of binary trees

n: number of nodes 6
number of non-null links: n-1 5
total links: 2n 12
null links: 2n-(n-1)=n+1 7

Replace these null pointers with some useful “threads”.

9/12/2024 111
 Threaded Binary Tree

The objective here to make effective use of these null pointers.

▪According to this idea we are going to replace all the null pointers by the
appropriate pointer values called threads.

▪And binary tree with such pointers are called threaded tree.

▪In the memory representation of a threaded binary tree, it is necessary to

distinguish between a normal pointer and a thread.

9/12/2024 112
 Threaded Binary Tree
Threading Rules

◦ RightChild null link at node p is replaced by the inorder successor of p.

◦ LeftChild null link at node p is replaced by the inorder predecessor of p.

9/12/2024 113
 Threaded Tree

B C

D E F G

H I

Inorder sequence: H, D, I, B, E, A, F, C, G

9/12/2024 114
 Threads
To distinguish between normal pointers and threads, two Boolean fields,
LeftThread and RightThread, are added to the record in memory representation.

9/12/2024 115
 Threaded Binary Tree
▪Therefore we have an alternate node representation for a threaded binary tree
which contains five fields as show bellow:

9/12/2024 116
 Threaded Binary Trees (Continued)
If ptr->left_child is null,
replace it with a pointer to the node that would be
visited before ptr in an inorder traversal

If ptr->right_child is null,
replace it with a pointer to the node that would be
visited after ptr in an inorder traversal

9/12/2024 117
 A Threaded Binary Tree
root A
dangling
B C

dangling D E F G

inorder traversal:
H I H, D, I, B, E, A, F, C, G

9/12/2024 118
 Threads (Contd...)
•To avoid dangling threads, a head node is used in representing a binary tree.

•The original tree becomes the left subtree of the head node.

9/12/2024 119
 Memory Representation of Threaded Tree
t - t

t A t

t B t t B t

t D t f E f f D f f E f

f H f f I f

9/12/2024 120
 main(){
tbtnode *head;
Allocate memory for head;
struct tbtnode{ rbit = 1;
char data; lbit = 0;
int rbit, lbit;
head->left = head-> right = head;
tbtnode *rightc;
tbtnode *leftc; create(head);
}; inorder(head);
preorder(head);
}

9/12/2024 121
Algorithm create(tbtnode *head) while(flag==0)
{ {
Allocate memory for root; Accept choice left or right;
Accept root data; if ch1='l’
Assign head lbit to 1; {
Assign root->leftc and rightc to head; if(temp->lbit==0)
Assign root->lbit and rbit to 0; {
Assign head->leftc to root;
curr->rightc=temp;
do curr->leftc=temp->leftc;
{ temp->leftc=curr;
Initialize flag to 0; temp->lbit=1;
temp=root; flag=1;
Allocate memory to curr and accept curr->data; }
Assign curr->lbit and rbit to 0; else
temp=temp->leftc;
}// end if for left
9/12/2024 122
 t - t
if(ch1=='r')
{
if(temp->rbit==0) t A t
{
curr->leftc=temp; t B t t C t
curr->rightc=temp->rightc;
temp->rightc=curr;
temp->rbit=1; t D t f E f f F f f G f
flag=1;
}
f H f f I f
else
temp=temp->rightc;
} // end if for right
} //end while flag
Accept choice for continue;

}while(ch=='y');
} //end algo
9/12/2024 123
Algorithm inorder(tbtnode *head) t - t
{
temp = head;
while(1) t A t
{
temp=inordersucc(temp);
if(temp == head) break; t B t t B t
print temp->data;
} t D t E f
f f D f f E f
}
Algorithm node * inordersucc(temp) f H f f I f
{
x=temp->right;
if(temp->rbit==1)
{
while(x->lbit==1)
x=x->left;
}
return x;
}
9/12/2024 124
 t - t
Algorithm preorder(tbtnode *head)
{
Assign temp to head->left; t A t
while(temp != head)
{
t B t t B t
print temp->data;
while(temp->lbit != 0)
{ t D t f E f f D f f E f
move temp to temp->left;
print temp->data;
f H f f I f
}
while(temp->rbit == 0)
move temp to temp->right;
move temp to temp->right;
}

9/12/2024 125
 Advantages of threaded binary tree:
◦ The traversal operation is more 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 stack
management.

◦ We can efficiently determine the predecessor and successor nodes starting from any node. In case of
unthreaded binary tree, however, this task is more time consuming and difficult.

◦ 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 their 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 from root.

9/12/2024 126
 Threaded Binary Tree
Disadvantages of threaded binary tree:

• Insertion and deletion from a threaded tree are very time consuming operation compare
to non-threaded binary tree.

• This tree require additional bit to identify the threaded link.

9/12/2024 127
Practice Problems
[Link] a pointer to the root of a binary tree, print the top view of the binary
tree.
The tree as seen from the top the nodes, is called the top view of the tree.
For example :
Sample Input: Sample Output- 1->2->5->6

9/12/2024 142
 2. You are given pointer to the root of the binary search tree and two values v1 and v2 .
You need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search
tree.

In the diagram above, the lowest common ancestor of the nodes 4 and 6 is the node 3.
Node 3 is the lowest node which has nodes 4 and 6 as descendants.

9/12/2024 143
 3. Given a tree and an integer, k, in one operation, we need to swap the subtrees of all the nodes at each
depth h, where h ∈ [k, 2k, 3k,...]. In other words, if h is a multiple of k, swap the left and right subtrees of
that level.
You are given a tree of n nodes where nodes are indexed from [1..n] and it is rooted at 1. You have to
perform t swap operations on it, and after each swap operation print the in-order traversal of the
current state of the tree.

Input Format
The first line contains n, number of nodes in the tree.
Each of the next n lines contains two integers, a b, where a is the index of left child, and b is
the index of right child of ith node.
Note: -1 is used to represent a null node.

Output Format
Sample Input 0
For each k, perform the swap operation and store the indices of your in-order traversal to your
result
3 array.
2After
3 all swap operations have been performed, return your result array for printing.
-1 -1
-1 -1
2
1
1
Sample Output 0
312
213
9/12/2024 144