Chapter - Three

Data Structure
and its
applications
 Types of Data
Structures
▶ There are two broad types
of data structure based on
their memory allocation:
▶ Static data structure
▶ Dynamic data structure
 Static Data
Structures
▶ Are data structures that are
defined & allocated before
execution, thus the size cannot
be changed during time of
execution.

Example:
Array implementation of
ADTs.
 Dynamic Data
Structure
▶ Are data structure that can
grow and shrink in size or
permits discarding of
unwanted memory during
execution time.

Example:
Linked list implementation of
ADTs.
 Structure
▶ Is a collection of data items and the data
items can be of different data type.

▶ The data item of structure is called

member of the structure.
Declaration of structure

▶ Structure is defined using the struct

keyword.
struct name {
data type1 member 1;
data type2 member 2
.
.
}; type n member n;
data
Example :

struct student {
char
name[20];
int

age;
char
Dept[20];
};
▶ The struct keyword creates a new
user defined data type that is used
to declare variable of an aggregated
 Accessing Members of Structure Variables

▶ The Dot operator (.): to access data

members of structure variables.

▶ The Arrow operator (->): to access

data members of pointer variables
pointing to the structure.

Example:
struct student stud;
struct student *studptr;

cout<<[Link];
OR
cout<<studptr->name; 7
 Linked
▶
List
Is self-referential structure.
▶ Is a collection of elements called nodes,
each of which stores two types of fields. Data
items and a pointer to next node.
The data field: holds the actual elements on
the list.
The pointer field: contains the address of the
next node in the list.
 Variations of Linked
Lists
1. Single linked lists: is the simplest type of
linked list in which every node contains some
data and a pointer to the next node of the same
data  It contain two "buckets" in one node; one
type.
bucket holds the data and the other bucket
holds the address of the next node of the
list.
 Traversals can be done in one direction
only as there is only a single link between
two nodes of the same list.

 Head: Special pointer that points to the first

node of a linked list, so that we can keep track
of the linked list.

 The last node should points to NULL to show

Variations of Linked
Lists…….

2. Circular linked lists: is a linked list

where all nodes are connected to form a
circle.
 In this linked list, the first node and the last node
are connected to each other which forms a circle.
There is no NULL at the end.
3. Doubly linked lists/ two-way linked
list - is a more complex type of linked list that
contains a pointer to the next as well as the
previous node in sequence.
 Each node points not only to Successor node
(Next node), but also to Predecessor node
(Previous node).
 There are two NULL: at the first and last nodes
in the linked list.
 Advantage: given a node, it is easy to visit its
predecessor (previous) node. It is convenient
to traverse linked lists Forwards and
Backwards.
 Operations of Linked List
Defining the data structure for
linked lists

//Single linked list

struct student
{
char name[20];
int age;
char Dept[20];
student *next;
};
struct student
*start = NULL;
 Defining the data
structure for
//Double linked list
linked lists
struct student
{
char name[20];
int age;
char Dept[20];
student *next;
student *prev;
};
struct student *start = NUL 15

L;
Adding a
node
Steps
to the
list
1. Allocate a new node.
2. Set the node data values and make
new node point to NULL.

3. Make old last node’s next pointer point

to the new node.
4. *Make the new last node’s prev pointer
point to the old last node. (This is only
for Double Linked list).
Traversing through
the listForward:
To Move

▶ Set a pointer to point to the same thing

as the
start (head) pointer.

▶ If the pointer points to NULL, display

the message “list is empty" and
stop.

▶ Otherwise, move to the next node by

making the pointer point to the same
thing as the next pointer of the node it
is currently indicating.
To Move Backward: (Single
linked list)
1. Set a pointer to point to the same thing

as the start pointer.

2. If the pointer points to NULL, display the

message “list is empty" and stop.

3. Set a new pointer and assign the same

value as start pointer and move forward
until you find the node before the one
we are considering at the moment.
To Move Backward: (Double
linked list)
1. Set a pointer to point to the same thing
as the
end (tail) pointer.

2. If the pointer points to NULL, display

the message “list is empty" and
stop.

3. Otherwise, move back to the previous

node by making the pointer point to
the same thing as the prev pointer of
the node it is currently indicating.
 Display the content
of list
Steps:

1. Set a temporary pointer to point to the same

thing as the start pointer.
2. If the pointer points to NULL, display the
message "End of list" and stop.
3. Otherwise, display the data values of the
node pointed to by the start pointer.
4. Make the temporary pointer point to the same
thing as the next pointer of the node it is
currently indicating.
5. Jump back to step
2.
Insert at the front
(beginning)
1. Allocate a
new node.
2. Insert new
element values.
3. Make the next
pointer of the
new node point
to old head
(start).
4. Update head
(start) to point
to the new node.
2
1
Inserting at the End
Steps
1. Allocate a new node.
2. Set the node data values and
make the next pointer of the new
node point to NULL.
3. Make old last node’s next pointer
point to the new node.
4. Update end to point to the new
node.
Insertion in the
middle
Steps:
▶Create a new Node

▶ Setthe node data

Values

▶Break pointer
connection

▶Re-connect the
pointers
 Assignment
 Write full implementation for doubly linked lists and
Circular lists.
 Your implementation should support the following
operations
Adding element/node
At the beginning
At the end
At the middle/specific location
 Deleting data/node
 From front
 From end
 From middle
 Displaying the list elements
 Stacks & its
Applications
 Introduction
 Stack is a data structure provides
temporary storage in such a way that the
element stored last will be retrieved first.
 All deletions and insertions occur at
one end of the stack known as the
TOP.
 Data going into the stack first, leaves
out last.
 Stacks are also known as LIFO data
structures (Last-In, First-Out).
 Basic Stack
Operations
 Push() – Adds an item to the top
of a stack.

 Pop() – Removes an item from

the top of the stack and returns
it to the user.

 Peek() – Copies the top item of

the stack and returns it to the
user; the item is not removed,
hence the stack is not altered.
Basic Stack Operations…….
 isEmpty(): return true if and only if the
stack is empty
 isfull(): return true if and only if the
stack is full

 createStack(): make an empty stack

(remove existing items from the stack
and initialize the stack to empty)

Note:- The operations of insertion and

deletion are called PUSH and POP
respectively.
Stacks are more restricted List with the
following constraints:
 Elements are stored by order of Stack
insertion
from "bottom" to "top“. ….
 Items are added to the top.
 Only the last element added onto the
stack (the top element) can be accessed
or removed.
Stacks in computer science
 The stack is one of the most important
data structures in all of computer
science
Function/method calls are placed onto a
stack.
Compilers use stacks to evaluate expressions.
Stacks are great for reversing things,
matching up related pairs of things, and
backtracking algorithms.
Stacks in computer science……
 Stack programming problems
 Reverse letters in a string, reverse words in a line, or
reverse a list of numbers.
 Find out whether a string is a palindrome (words read
forward and backward similarly) (Example: madam, lol,
pop, radar)
 Examine a file to see if its braces { } and other
operators match.
 Stack Application
 Reversing data
 Converting decimal to binary
Stack has at least the following operation:
 Push an element to the top of the stack
 Pop an element from the top of the stack
 Display the content of the top element in the
stack
 Display the content of all elements in the stack
forward manner
 Display the content of all elements in the stack
backward manner
Push an element to the top of the stack in an
Array
void push()
{
int val;
if(r==n-1)
cout<<"Stack Overflow"<<endl;
else
{
if(f==-1)
f=0;
cout<<"Insert an element to push : "<<endl;
cin>>val; // 9
r++;
s[r] = val;
}
}
Pop an element from the top of the stack in an array
void pop()
{
if(f==-1||f>r)
{
cout<<"Stack Underflow ";
return; //exist if the condition is true
}
else
{
cout<<"Element popped off from stack is :
"<<s[r]<<endl;
r--;
}
}
Display the content of the top element in the stack in an
array
void displayTop()
{
if(f==-1)
cout<<"Stack is empty"<<endl;
else
{
cout<<"The top element in the Stack is : ";
cout<<s[r]<<" ";
cout<<endl;
}
}
Display the content of all elements in the stack forward
void displayForward()
{
if(f==-1)
cout<<"Stack is empty"<<endl;
else
{
cout<<"Stack elements are : ";
for(int i=f;i<=r;i++)
cout<<s[i]<<" ";
cout<<endl;
}
}
Display the content of all elements in the stack back manner in an
array
void displayBackward()
{
if(r==-1)
cout<<"Stack is empty"<<endl;
else
{
cout<<"Stack elements are : ";
for(int i=r;i>=f;i--)
cout<<s[i]<<" ";
cout<<endl;
}
}
 Applications of stacks
For evaluation of Algebraic Expressions
Expression can be evaluated by machine by placing all
operators before or after their operands this method is
called polish notation
Example: 4 + 5 * 5
 Simple calculator: 45 OR
 Scientific calculator: 29 (correct), but how? Because
computers solve arithmetic expressions by
restructuring them from infix to “post-fix notation”
also called reverse-polish notation (RPN).
The valuable aspect of RPN (Reverse Polish
Notation or postfix )
 Parentheses are unnecessary
 Easy for a computer (compiler) to evaluate an
arithmetic expression
 There are three kinds of expressions
Infix notation:
 It is the normal (human-readable) way of expressing
mathematical expressions.
 Operators are written in between their operands.
e.g. 4 + 5 * 5
Prefix notation:
 Also called by its inventor as “Polish Notation”
 Operators are written before their operands.
e.g. + 4 * 5 5
Postfix notation:
 Operators are written after their operands
 Also called suffix notation or reverse polish
notation (RPN).
e.g. 4 5 5 * +
 Rules of Infix to Postfix conversion
Rules:
 Operands immediately go directly to output (postfix).
 Operators are pushed into the stack (including
parenthesis, but not as output)
 Check to see if stack top operator is less than current
operator
 If the top operator is less than, push the current operator
onto stack
 If the top operator is greater than (or equal to) the current,
pop top operator and append on postfix notation, push
current operator onto stack.
 If we encounter a right parenthesis, pop from stack until
we get matching left parenthesis.
 Any operators comes after parenthesis push the current
operators
Precedence Priority of operators: High to Low
 Priority 4: ‘(‘ - only popped if a matching ‘)’ is found.
 Priority 3: All unary operators (-, sin, cosin, ….) and
exponents
 Priority 2: / *
 Example
A + B * C - D /
1: E
Infix
Stack(bottom->top) Postfix
A + B * C - D / E empty empty
+ B * C - D / E empty A
b) B * C - D / E + A
c) * C - D / E + A B
d) C - D / E + * A B
e) - D / E + * A B C
f) D / E + - A B C *
g) / E + - A B C * D
h) E + - / A B C * D
i) + - / A B C * D E
j) empty A B C * D E / - +

39
 Here are some examples of infix and the
corresponding postfix expressions:

infix postfix
(A+B*C) ABC*+
(A*(B+C)/D-E) ABC+*D/E-
(A+B*(C-D*(E-F)-G*H)-I*3) ABCDEF-*-
GH*-*+I3*-
(A+B*C/D*E-F) ABC*D/E*+F-
(A+B+C*D-E*F*G)
AB+CD*+EF*G*-
(A+(B-(C+(D-(E+F))))) ABCDEF+-+-+
(A*(B+(C*(D+(E*(F+G))))))
ABCDEFG+*+*+*
 Exercise
Evaluate the expression 2 3 4 + * 5 *
= 70
 if operand is encountered push it into stack
53+62/*35*+
 if operator is encountered pop 2 operands from
stack and perform arithmetic.
 A top element
 B next to top element
 Result =B operator A
 Push result on to stack
 Return to the top of the stack
 Queue
▶ Many times, we use a list in a way where we
always add to the end, and always remove from
the front.
▶ The first element put into the list will be
the first element we take out of the list:
First-In, First-Out ("FIFO")
▶ Queue is a more restricted List with the
following constraints:
o Elements are stored by order of insertion from
front to back.
o Items can only be added to the back of the
queue.
o Only the front element can be accessed or
removed.
 Queue … (continued)

Operations on a queue
▶ Offer or enqueue: add an element to the back.
▶ Remove or dequeue: remove and return the element at
the
front.
▶ peek: return (but not remove) front element:
▶ peek on an empty queue returns null.
▶ Other operations: isEmpty, size.
Queue features
▶ ORDERING: maintains order elements were
added (new elements are added to the end
by default).
 Queue cont.……

OPERATIONS:
▶ Add element to end of list ('offer'
▶

or 'enqueue').
▶ Remove element from beginning of
list ('remove' or 'dequeue')
examine element at beginning of
list ('peek').
▶ Clear all elements.
▶ is empty, get size.
 The Queue
Operations
▶A queue is like a line of people waiting for a
bank teller. The queue has a front and a
rear.

$ $

Front
Rear
 The Queue Operations

▶ New people must enter the

queue at the rear. it is
usually called an
enqueue operation.
$ $

Front

Rear
 The Queue
Operations
▶ When an item is taken from the
queue, it always comes from
the front. it is usually called a
dequeue operation.

$ $

Front
Rear
Array
Implementation of
Queue
▶ A queue can be implemented with an
array, as shown here. For example,
this queue contains the integers 4 (at
the front), 8 and 6 (at the rear).

[0] [1] [3] [4] [5]

[2] ...
4 8 6

An array of integers
to implement a We don't care what's in
queue of integers this part of the array.
1. Simple Array Implementation of
Queue
▶ The easiest implementation
also keeps track of the
number of items in the queue
(Queue Size) and the index of
3 size
the first element (at the front
of the queue), the last element
(at the rear). 0 first

2 last

[0] [1] [2] [3] [4] [5] ..

.
4 8 6 1
Front Rear 0
 A Dequeue
Operation
▶ When an element leaves the
queue, size is decremented,
and first changes, too. 2 size

1 first

2 last
[0] [1] [2] [4] [5]
[3] ...
4 8 6

Front Rear
 An Enqueue
Operation
▶ When an element enters the
queue, size is incremented,
3 size
and last changes, too.

1 first

3 last

[0] [1] [2] [3] [4] [5]

...
8 6 2
1
2
Front Rear
2. Circular Array
Implementation of Queue
▶There is special behaviour at
the end of the array. For 3 size
example, suppose we want
to add a new element to this
queue, where the last index 3 first
is [5]:
5 last

[0] [1] [2] [4]

[3] [5]
2 6 1
1
3 Rear
Front
 An Enqueue
Operation
▶ The new element goes at the
front of the array (if that 4 size
spot isn’t already used):
3 first

0 last
[0] [1] [2] [3] [4]
[5]
4 2 6 1
14
Rear
Front
Linked List
Implementation
▶A queue can also be implemented
with a linked list with both a head
(start) and a tail (end) pointer.
▶Enqueue:- is inserting a node at
the end of a linked list.
▶Dequeue:- is deleting the first
node in a linked list.
 13 10 15
null

head_ptr
tail_ptr
Types of
Queue
Deque (pronounced as
Deck)
▶ Is a Double Ended Queue.
▶Insertion and deletion can occur at either
end.
▶ Has the following basic operations:
EnqueueFront:– inserts data at the front
of a list.
DequeueFront:– deletes data at the front
of a list. EnqueueRear:– inserts data at
the end of a list.
DequeueRear:– deletes data at the end
of a list.
▶ Implementation is similar to
that of queue.
▶ Is best implemented using doubly
linked list.

Front Rear

DequeueFront EnqueueFront DequeueRear EnqueueRear

2
0
 Priority Queue
▶ Is a queue where each data has an
associated key that is provided at the
time of insertion.

▶ Dequeue operation deletes data

having highest priority in the list.

▶ One of the previously used

dequeue or enqueue operations
has to be modified.
Example: Consider the following queue
of persons where females have
higher priority than males (gender is
the key to give priority).

Abebe Alemu Aster Belay Kedir Meron Yonas

Male Male Female Male Male Female Male
▶Dequeue()- deletes
Aster.
Abebe Alemu Belay Kedir Meron Yonas
Male Male Male Male Female Male

▶Dequeue()- deletes
Meron
Abebe Alemu Belay Kedir Yonas
Male Male Male Male Male
▶ Now the queue has data having equal
priority and dequeue operation deletes
the front element like in the case of
ordinary queues.
▶Dequeue():- deletes
Abebe

Alemu Belay Kedir Yonas

Male Male Male Male
▶ Dequeue():- deletes
Alemu
Belay Kedir Yonas
Male Male Male

▶ Thus, in the above example the

implementation of the dequeue
operation need to be modified.
Demerging Queues:
▶Is the process of creating two
or more queues from a single
queue.
▶Used to give priority for
some groups of data
Example: The following two
queues can be created from
the above priority queue.

Aster Meron

Female Female

Abebe Alemu Belay Kedir Yonas

Male Male Male Male Male
 Algorith
m:
create empty females and males queue
while (PriorityQueue is not empty)
{
Data=DequeuePriorityQueue();//delete data at
the front
if(gender of Data is Female)
EnqueueFemale(Data);
else
EnqueueMale(Data);
}
Merging Queues:
▶Is the process of creating a
priority queue from two or
more queues.
▶The ordinary dequeue
implementation can be used
to delete data in the newly
created priority queue.
Example: The following two queues
(females queue has higher priority
than the males queue) can be
merged to create a priority queue.

Aster Meron Abebe Alemu Belay Kedir Yonas

Female Female Male Male Male Male Male

Aster Meron Abebe Alemu Belay Kedir Yonas

Female Female Male Male Male Male Male
 Algorithm:

create an empty priority queue

while(FemalesQueue is not
empty)
EnqueuePriorityQueue(DequeueFemalesQue
while(MalesQueue is not empty)
ue());

EnqueuePriorityQueue(DequeueMalesQueue());
 Application of
Queues
1. Access to shared resources
(Example: printer)

Print()
{
EnqueuePrintQueue(Document)
}
EndOfPrint()
{
DequeuePrintQueue()
}
Application of Queues
(...Continued)

II. Disk Driver:-maintains a queue

of disk input/output requests.

III. Task scheduler in

multiprocessing system
maintains priority queues of processes.

IV. Telephone calls in a busy

environment
maintains a queue of telephone
calls.
TREE
 There are two classifications of data structures:
Linear Data Structures:
A data structure is said to be linear, if its elements form a
sequence or linear list.
Example: Arrays, linked lists, Stacks, and Queues.

Non-linear Data Structures:

A Data Structure is said to be non-linear, if its
elements do not form a sequence.
Example: Trees and Graphs.
TREE
 A tree is a set of nodes and edges
that connect pairs of nodes.

 Rooted tree has the following

structure:
 One node distinguished as root.
 Every node C except the root is connected from
exactly other node P. P is C's parent, and C is
one of P's children.
 There is a unique path from the root to each
node.
 The number of edges in a path is the length
of the path.
Tree Terminologies
 Consider the following tree.
ABEFGCDHIJKLM.

C D H I J

K L M
Root: a node with out a parent.
A
Internal node: a node with at least one
child.

A, B, F, I, J
External (leaf) node: a node without a
child.

 C, D, E, H, K, L, M, G
Ancestors of a node: parent, grandparent,
grand- grandparent, etc of a node.

Ancestors of K  A, F, I
Descendants of a node: children, grandchildren,
grand-grandchildren etc of a node.
Descendants of F  H, I, J, K, L, M

Depth of a node: number of ancestors or length

of the path from the root to the node.
Depth of H  2
Height of a tree: depth of the deepest node.
3
Subtree: a tree consisting of a node and its
descendants.
A
F

B E F G
H I J
C D H I J
K L M
K L M
Binary tree: a tree in which each node
has at most two children called left
child and right child.
Binary Tree …(continued)
Full binary tree: a binary tree
where each node has either 0 or 2
children.
Balanced binary tree: a binary tree
where each node except the leaf nodes
has left and right children and all the
leaves are at the same level.
Complete binary tree: a binary tree in
which the length from the root to any leaf
node is either h or h-1.
 where h is the height of the tree.
 The deepest level should also be filled
from left to right.
Binary search tree (ordered
binary
 tree)
A binary tree that may be empty, but if
it is not empty it satisfies the following.

 Everynode has a key and no two

elements have the same key.

 The keys in the right subtree are larger

than the key in the root.

 The keys in the left subtree are smaller

than the key in the root.

 The left and the right subtrees are also

binary search trees.
Examples of Binary Search
Tree.

10
6 15

4 8 14 18

7 12 16 19

11 13
 Exercise
Insertion
Draw Binary search tree by inserting the
following key values from left to right
11,6,8,19,4,10,5,17,43,49,31

Deletion
If the root node is deleted, then how to insert another
node in to the tree.
1. Inorder predecessor(the larger number from left sub
tree)
2. Inorder successor(the smaller number from right sub
tree)
Binary Search Tree …(continued)

▶ Here are some Binary Search Trees in

which each node just stores an integer
key:
 Binary Search Tree …(continued)
▶ These are not Binary Search
Trees:

▶ In the left one 5 is not greater than 6.

In the right one 6 is not greater than 7.
 Binary Search Tree …
(continued)

 Note that more than one Binary Search

Tree can be used to store the same set
of key values.
 For example, both of the following are
BSTs that store the same set of integer
keys:
 Binary Search Tree …
(continued)

▶The reason Binary-Search Trees are important

is that the following operations can be
implemented efficiently using a Binary Search
Tree:
▶Insert a key value.
▶Determine whether a key value is in the
tree.
▶Remove a key value from the tree.
▶Print all of the key values in sorted order.
 Data Structure of a Binary
Tree Syntax: struct DataModel
{
Declaration of data
fields DataModel * Left,
*Right;
};
DataModel
*RootDataModelPtr=N
ULL;
Example:
struct Node
{
int Num;
Node * Left, *Right;
};
Node
*RootNodePtr=NULL;
 Operations on Binary Search Tree
 Consider the following definition of binary search tree.
struct Node
{
int Num;
Node * Left, *Right;
};
Node *RootNodePtr=NULL;
 Insertion
▶ When a node is inserted the definition of binary
search tree should be preserved.

▶ Suppose there is a binary search tree whose

root node is pointed by RootNodePtr.

▶ We want to insert a node (that stores 17)

pointed by
InsNodePtr.
Case 1: There is no data in the tree:
(i.e. RootNodePtr is NULL)

 The node pointed by InsNodePtr should

be made root node.

RootNodePtr RootNodePtr
InsNodePtr

17
17
Case 2: If there is data in the
tree: 
Search the appropriate position.
 Insert the node in that position.
RootNodePtr
InsNodePtr RootNodePtr

InsertBST(RootNodePtr, InsNodePtr) 
17 10 10

6 15 6 15

4 8 14 4 8 14
18 18

7 12 12
16 19 7 16 19

11 13 13 17
11
 Traversi
▶
ng
Binary search tree can be traversed in three ways.

 Preorder traversal:- traversing binary tree in

the order of parent, left and right.

 Inorder traversal:- traversing binary tree in the

order of left, parent and right.

 Postorder traversal:- traversing binary tree in

the order of left, right and parent.
Exampl
e:

Preorder traversal:10, 6, 4, 8, 7, 15, 14, 12, 11, 13, 18, 16, 17, 19
Inorder traversal:4, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17
18,19
Used to display nodes in ascending order.
Postorder traversal:4, 7, 8, 6, 11, 13, 12, 14, 17, 16, 19, 18, 1
10
 Exercise
Construct Binary search tree from the given
Preorder and Postorder traversal
Preorder - 20,16,5,18,17,19,60,85,70
Postorder – 5,17,19,18,16,70,85,60,20
 Application of binary tree traversal

▶ Store values on leaf nodes and operators on internal

nodes:
 Preorder traversal: - used to generate mathematical
expression in prefix notation.

 Inorder traversal: - used to generate mathematical

expression in infix notation.

 Postorder traversal: - used to generate mathematical

expression in postfix notation.
 +
Exampl
e: – +

A * D /

B C E F

Preorder traversal: + – A * B C + D / E F  Prefix notation

Inorder traversal: A – B * C + D + E / F  Infix notation A
Postorder traversal: B C * – D E F / + +  Postfix notation

3
0
Preorder traversal
[Link] the value in the root (e.g. print the root value).
[Link] the left subtree with a preorder traversal.
[Link] the right subtree with a preorder traversal.
Inorder traversal :- prints the node values in ascending
order:
[Link] the left subtree with an inorder traversal.
[Link] the value in the root (e.g. print the root value).
[Link] the right subtree with an inorder traversal.

Postorder traversal
[Link] the left subtree with a postorder traversal.
[Link] the right subtree with a postorder traversal.
[Link] the value in the root (e.g. print the root value).
Exercise
Find the Preorder, Inorder and
Postorder traversal of the given
binary tree.
 Searchin
g
▶ To search a node (whose Num value is X) in
a binary search tree (whose root node is
pointed by RootNodePtr).

▶ One of the three traversal methods can be

used.
 RootNodePtr

10

6 15

4 8 14 18

7
12 16 19

11 13 17
Implementati
on:
int SearchBST (Node *RootNodePtr, int X)

if(RootNodePtr == NULL)

return 0; // 0 means (false, not

found). else if(RootNodePtr Num == X)

return 1; // 1 means (true,

found). else if(RootNodePtr Num > X)

return(SearchBST(RootNodePtr Left, X));

else
return(SearchBST(RootNodePtr Right,
X));
}
Finding Minimum
value in a Binary
Search Tree
▶ We can get the minimum value
from a Binary Search Tree, by
locating the left most node in
the tree.

▶ Then after locating the left most

node, we display the value of that
node.
 RootNodePtr

10
Minimum
6 15

4 8 14 18

7
12 16 19

11 13 17
 Implementation:

int findMin(Node
*RootNodePtr)
{ if(RootNodePtr == NULL)
return -1;
else if(RootNodePtr ->Left ==
NULL) return RootNodePtr -
>Num;
else
return findMin(RootNodePtr -
>Left);
}
Finding Maximum
value in a Binary
Search Tree
▶ We can get the maximum value
from a Binary Search Tree, by
locating the right most node
in the tree.

▶ Then after locating the right

most node, we display the
value of that node.
 RootNodePtr

10

6 15
Maximum
4 8 14 18

7 12 16 19

11 13 17
Implementati
on:
int findMax(Node
*RootNodePtr) { if(RootNodePtr
== NULL)
return -1;
else if(RootNodePtr ->Right ==
NULL) return RootNodePtr ->Num;
else
return findMax(RootNodePtr -
>Right);
}
Exercise
M

A Y E

J R H

P Q T

Traverse the above tree

 Breadth first
 Depth First
 Preorder
 Inorder
 Postorder
Thank
You