DATA STRUCTURES

PAPER 1 CHAPTER 2
 NAME FIRST NAME MIDDLE NAME LAST NAME group item

DIVISION elementary item

ROLL NUMBER

ADDRESS ADDRESS 1 ADDRESS 2 ADDRESS 3

STATE

PINCODE

MOBILE

EMAIL ID

STREAM

attributes values
 NAME X Y Z

DIVISION J
ROLL NUMBER 1

ADDRESS SIES COLLEGE JAIN SOCIETY SION

STATE MAHARASHTRA

PINCODE 400022

MOBILE 1332456879

EMAIL ID xyz@[Link]

STREAM science

RECORD
• DATA : Data are simply values or set of values
• GROUP ITEMS : Data items which are divided into subitems are called
as group items.
• ELEMENTARY ITEMS : Data items which are not divided into subitems
are called as elementary items .
• ENTITY : An entity is something that has certain attributes or
properties which may be assigned values. Values may be numeric or
nonnumeric.
• FIELD : Field is a single elementary unit of information representing
an attribute of an entity.
• RECORD : Record is a collection of field values of a given entity .
• FILE : File is a collection of records of the entities in a given entity set.
• Data may be organized in many different ways.
• Data structure is the way in which different data elements are
logically related.
• Types
1. Linear data structure
2. Non – linear data structure
• Linear data structure : data elements are stored in consecutive
memory locations or by using linked representation e.g. arrays ,
linked lists.
• Non – linear data structure : linear order cannot be maintained
between data elements .Data elements have hierarchical
relationship between them e.g. Trees.
Data Structure operations :
1. Traversing – Accessing each record or element exactly once , so that
it can be processed is called as traversing.
2. Inserting – Adding a new record to the existing structure is called as
inserting.
3. Deleting - Removing a record from the existing structure is called as
deleting.
4. Searching – Finding the location of a record with given key values or
finding the locations of all records which satisfy one or more
conditions is called as searching.
5. Sorting – Arranging records in some logical order is called as sorting.
6. Merging – Merging means combining the records in two different
sorted files into a single sorted file .
 Iteration logic
conditional flow or selection logic conditional flow or selection logic
sequential logic single alternative double alternative

Module A
if no if if
no
conditi condition condition
on ? ? ?
Module B
yes Module B
yes
Module C Module A Module A Module

If condition then :
If condition then :
Module A
Module A
Else : Repeat While condition :
End of If structure
Module B Module
End of If structure End of loop
 KR

yes
if K > S ?

Repeat For K = R to S by T :
Module
no
End of For loop
Module K is called index variable
R and S are initial and final values of K
T is increment value

KK+T
Algorithm :
An algorithm is a finite step by step list of well defined
instructions for solving a particular problem
An algorithm consists of two parts :
• First part is a paragraph which tells the purpose of algorithm.
In this part, we define variables in algorithm and lists the input
data
• The second part of algorithm consists of steps in algorithm that
are executed one after the another, generally beginning with
step 1, unless stated otherwise. The control can be transferred
to step n, by the statement ‘go to step n’. The algorithm is
completed, when the statement ‘Exit’ or ‘Stop’ is encountered.
• Traversing an array means accessing
each element of array atleast once , so
that it can be processed. LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9]
• Algorithm : 10 20 30 40 50 60 70 80 90 100

• Here LA is a linear array with lower LB = 0 , UB = 9 PROCESS : LA[K] *5 , K = 0

bound LB and upper bound UB. While K < = 9
Following algorithm applies operation LA[ 0 ] = 10*5 = 50 , K = 1
LA[ 1 ] = 20*5 = 100 , K = 2
PROCESS to each element of LA. LA[ 2 ] = 30*5 = 150 , K = 3
STEP 1. [Initialize counter] Set K := LB LA[ 3 ] = 40*5 = 200 , K = 4
LA[ 4 ] = 50*5 = 250 , K = 5
STEP 2. Repeat steps 3 and 4 while K <= UB LA[ 5 ] = 60*5 = 300 , K = 6
: LA[ 6 ] = 70*5 = 350 , K = 7
LA[ 7 ] = 80*5 = 400 , K = 8
STEP 3. [Visit element] LA[ 8 ] = 90*5 = 450 , K = 9
Apply PROCESS to LA[K] LA[ 9 ] = 100*5 = 500 , K = 10

STEP 4. [Increment counter]

Set K:=K+1 LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9]
50 100 150 200 250 300 350 400 450 500
[End of step 2 loop]
STEP 5. Exit
• Inserting refers to the operation of adding an element
to the existing elements an array. LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9]

• The element can be easily added at the end of array . 10 20 30 40 50 60 70 80 90 100

But for insertion in the middle of array , it is required to
LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9] LA[10]
move the elements of array one byte forward .
• The following algorithm inserts a data element of the 10 20 30 40 50 60 70 80 90 100
array one byte forward .
LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9] LA[10]
• The following algorithm inserts a data element ITEM
into the Kth position in an array LA with N elements.
10 20 30 40 50 60 70 80 90 100
• Algorithm : INSERT ( LA , K , N ,ITEM)
LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9] LA[10]
• Here LA is a linear array with N elements and K is a
positive integer such that K <=N. Following algorithm 10 20 30 40 50 60 70 80 90 100
inserts an element ITEM at Kth position in LA.
LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9] LA[10]
STEP 1. [Initialize counter] . Set J := N - 1
STEP 2. Repeat steps 3 and 4 while J >=K. 10 20 30 40 50 60 70 75 80 90 100
STEP 3. [Move Jth element forward] . Set LA[J+1] := LA[J]
STEP 4. [Decrement counter] Set J := J – 1. [End of step 2 N = 10 , J = 9 , K =7 , ITEM = 75
loop] While J >= K
STEP 5. [Insert the element] Set LA [ K ] : = ITEM LA [ 10 ] = LA [ 9 ] , J = J - 1 = 8
LA [ 9 ] = LA [ 8 ] , J = J - 1 = 7
STEP 6.[Reset N] Set N := N + 1
LA [ 8 ] = LA [ 7 ] , J = J - 1 = 6
STEP 7. Exit LA [ 7 ] = 75
N = N + 1 = 11
• Deleting refers to the operation of LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9]
removing an element from the
existing elements an array. 10 20 30 40 50 60 70 80 90 100
• Deletion at the end of an array is LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9] LA[10]
easier. But , if to delete an element
from mid of array , then to move 10 20 30 40 50 60 80 90 100
the elements of array one location
upward. LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9] LA[10]

• Algorithm : DELETE ( LA , K , N 10 20 30 40 50 60 80 90 100

,ITEM)
• Here LA is a linear array with N LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9] LA[10]

elements and K is a positive integer 10 20 30 40 50 60 80 90 100

such that K <=N. Following
algorithm deletes Kth element
from LA and assigns it to variable
ITEM
STEP 1. Set ITEM := LA[K]
STEP 2. Repeat for J = K to N – 1 . N = 10 , K = 6
ITEM = LA [ 6 ] = 70
[Move (J+1)st element backward] .
J = 6 TO 8
Set LA[ J ] := LA [ J + 1 ] [ End of loop] LA [ 6 ] = LA [ 7 ] , J = J + 1 = 7
STEP 3. [ Reset N ] Set N := N - 1 LA [ 7 ] = LA [ 8 ] , J = J + 1 = 8
STEP 6. Exit LA [ 8 ] = LA [ 9 ] , J = J + 1 = 9
N=N-1=9
• Bubble sort refers to the operation of sorting DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]
elements of an array.
5 7 1 3 2
• Algorithm : BUBBLE SORT ( DATA , N )
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]
• Here DATA is a linear array with N elements .
This algorithm sorts elements of DATA in 5 7 1 3 2
ascending order. DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]
STEP 1. Repeat steps 2 and 3 for K := 0 to N - 1 5 1 7 3 2
STEP 2. Set Ptr := 0 DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]
STEP 3. Repeat While Ptr <= (N - 1) – K 5 1 3 7 2
(a) If DATA [ Ptr ] > DATA [ Ptr + 1 ] , then DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]
interchange
5 1 3 2 7
DATA [ Ptr ] and DATA[ Ptr+1 ]
[End of If structure] N = 5 , K = 0 TO 4 ,
K = 0 , Ptr = 0
(b) [Increment pointer] While Ptr <= (N - 1) – K → Ptr < = 4
If DATA [ 0 ] > DATA [ 1 ] SWAP , 5 < 7 DATA [ 0 ] = 5 DATA [ 1 ] = 7 Ptr = 1
Set Ptr := Ptr + 1 If DATA [ 1 ] > DATA [ 2 ] SWAP , 7 > 1 DATA [ 1 ] = 1 DATA [ 2 ] = 7 Ptr = 2
[ End of inner loop ] If DATA [ 2 ] > DATA [ 3 ] SWAP , 7 > 3 DATA [ 2 ] = 3 DATA [ 3 ] = 7 Ptr = 3
If DATA [ 3 ] > DATA [ 4 ] SWAP , 7 > 2 DATA [ 3 ] = 2 DATA [ 4 ] = 7 Ptr = 4
[ End of outer loop ]
STEP 4. Exit
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]

5 1 3 2 7 1 3 2 5 7 1 3 2 5 7
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] DATA[0] DATA[1] DATA[2] DATA[3] DATA[4]
1 3 2 5 7
1 5 3 2 7 1 3 2 5 7
N = 5 , K = 0 TO 4 ,
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] K = 3 , Ptr = 0
While Ptr <= (N - 1) – K → Ptr < = 1
1 3 5 2 7 1 2 3 5 7 If DATA [ 0 ] > DATA [ 1 ] SWAP , 1 < 3 DATA [0] =1 DATA [ 1 ] = 3
Ptr = 1
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] N = 5 , K = 0 TO 4 , If DATA [ 1 ] > DATA [ 2 ] SWAP , 2 < 3 DATA [1] = 2 DATA [ 2 ] = 3
K = 2 , Ptr = 0 Ptr = 2
1 3 2 5 7 While Ptr <= (N - 1) – K → Ptr < = 2
If DATA [ 0 ] > DATA [ 1 ] SWAP , 1 < 3 DATA [ 0 ] = 1 DATA [ 1 ] = 3 Ptr = 1
N = 5 , K = 0 TO 4 , If DATA [ 1 ] > DATA [ 2 ] SWAP , 3 > 2 DATA [ 1 ] = 2 DATA [ 2 ] = 3 Ptr = 2
K = 1 , Ptr = 0 If DATA [ 2 ] > DATA [ 3 ] SWAP , 3 < 5 DATA [ 2 ] = 3 DATA [ 3 ] = 5 Ptr = 3
While Ptr <= (N - 1) – K → Ptr < = 3
If DATA [ 0 ] > DATA [ 1 ] SWAP , 5 > 1 DATA [ 0 ] = 1 DATA [ 1 ] = 5 Ptr = 1
If DATA [ 1 ] > DATA [ 2 ] SWAP , 5 > 3 DATA [ 1 ] = 3 DATA [ 2 ] = 5 Ptr = 2
If DATA [ 2 ] > DATA [ 3 ] SWAP , 5 > 2 DATA [ 2 ] = 2 DATA [ 3 ] = 5 Ptr = 3 STEP 3. Repeat While Ptr <= N – K
If DATA [ 3 ] > DATA [ 4 ] SWAP , 5 < 7 DATA [ 3 ] = 5 DATA [ 4 ] = 7 Ptr = 4
(a) If DATA [ Ptr ] > DATA [ Ptr + 1 ] ,
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] Even though the then interchange
1 3 2 5 7 array is sorted the DATA [ Ptr ] and DATA[ Ptr+1 ]
process will [End of If structure]
N = 5 , K = 0 TO 4 ,
continue for K = 3 (b) [Increment pointer]
K = 4 , Ptr = 0
While Ptr <= (N - 1) – K → Ptr < = 0
Set Ptr := Ptr + 1
and K = 4 [ End of inner loop ]
If DATA [ 0 ] > DATA [ 1 ] SWAP , 1 < 3 DATA [ 0 ] = 1 DATA [ 1 ] = 3 Ptr = 1
• In linear search the given element is LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9]
compared with each element of list one
10 20 30 40 50 60 70 80 90 40
• Algorithm : LINEAR ( LA , N , ITEM ,
LOC ) ITEM = 40 , N = 9 , LA [ 9 ] = 40 , LOC = 0
LA [ 0 ] ≠ 40 , LOC = 1
• Here LA is a linear array with N LA [ 1 ] ≠ 40 , LOC = 2
elements and ITEM is given element . Element to be searched
LA [ 2 ] ≠ 40 , LOC = 3
This algorithm finds the location LOC of LA [ 3 ] = 40 , LOC = 4
ITEM in DATA or sets LOC = 0 , if search
is unsuccessful.
STEP 1. [ Insert ITEM at the end of DATA ] LA[0] LA[1] LA[2] LA[3] LA[4] LA[5] LA[6] LA[7] LA[8] LA[9]
Set LA [ N ] := ITEM 10 20 30 40 50 60 70 80 90 55
STEP 2. [ Initialize counter ] Set LOC := 0 ITEM = 55 , N = 9 ,LA [ 9 ] = 40 , LOC = 0
STEP 3. [Search for ITEM] LA [ 0 ] ≠ 55 , LOC = 1
Repeat While LA [ LOC] ≠ ITEM LA [ 1 ] ≠ 55 , LOC = 2
LA [ 2 ] ≠ 55 , LOC = 3
Set LOC : = LOC + 1 LA [ 3 ] ≠ 55 , LOC = 4
[End of loop] LA [ 4 ] ≠ 55 , LOC = 5
LA [ 5 ] ≠ 55 , LOC = 6
STEP 4. If LOC = N , then : LA [ 6 ] ≠ 55 , LOC = 7
Set LOC := 0 LA [ 7 ] ≠ 55 , LOC = 8
LA [ 8 ] ≠ 55 , LOC = 9
STEP 5. Exit. HENCE LOC = 0
• Binary search is used to search an element from sorted array.
DATA[0] DATA[1] DATA[2] DATA[3] DATA[4] DATA[5] DATA[6] DATA[7]
• Algorithm : BINARY SEARCH ( DATA , LB , UB , ITEM , LOC )

• Here DATA is a sorted array with lower bound LB and upper bound
UB. ITEM is given element. BEG denotes beginning , MID denotes 1 2 3 5 7 9 10 11
middle and END denotes end location of DATA. This algorithm finds
the location LOC of ITEM in DATA or sets LOC = 0 if search is
unsuccessful.

STEP 1. [Initialize Variables]

ITEM = 10 BEG = 0 END = 7 MID = INT ( 0 + 7 )/2 = INT ( 7 / 2 ) = 4
Set BEG:=LB , END := UB and MID := INT (( BEG + END )/2)
WHILE 0 <= 7 and DATA ( 4 ) ≠ 10
STEP 2. Repeat steps 3 and 4
10 > 7 , BEG = 5
while BEG<= END and DATA(MID) ≠ ITEM
MID = INT ( 5 + 7 )/2 =INT ( 12 / 2 ) = 6
STEP 3. If ITEM < DATA [MID] , then : WHILE 0 <= 7 and DATA ( 6 ) ≠ 10…… Here DATA[6] =10 HENCE exit while
Set END := MID – 1 and LOC = 6
Else :

Set BEG := MID +1

[ End of If structure]
STEP 4. Set MID := INT (( BEG + END )/2) [ End of STEP 2 loop]

STEP 5. If DATA [MID] = ITEM , then :

Set LOC : = MID

Else :

LOC := NULL

[ End of If structure]
STEP 6. Exit.
Advantages of Binary search :
1. It is efficient as the search scope gets reduced by half
the size of the array , with each iteration
2. The number of comparisons required are
approximately equal to log2n which are less than linear
search
Disadvantages of Binary search :
1. The given list must be sorted.
2. At each iteration middle element calculation is
required.
Linear Search Binary Search
1. Linear search is performed on unsorted 1. Binary search is performed on sorted
list of elements as well as sorted list. list of elements.
2. Compare the desired element with all 2. Compare the value of midpoint with
elements in an array until the match is desired element. If the value is greater
found. than midpoint value the first half is
checked , otherwise second half is
checked until search is unsuccessful or
interval is empty.
3. Insertion of an element in an array can 3. Insertion of an element in an array
be performed easily when array is not requires that many elements be
sorted. physically moved to preserve the order.
4. For large size array , time required is 4. For large size array , time required is
very large. less.
5. Time complexity is as follows : 5. Time complexity is as follows :
Worst case : N comparison Worst case : log2N comparison
Best case : 1 comparison Best case : 1 comparison
POINTER ARRAYS :
• An array is called pointer array , if each element of that array is a pointer.
• The variable is called a pointer variable , if it points to another variable i.e. it contains the memory address of another variable
FRUIT VEGETABLE PULSES MILK POINTER ITEM
PRODUCTS 1 APPLE
APPLE TOMATO MOONG CREAM 2 MANGO
MANGO POTATO RAJMA CHEESE 3 ORANGE GROUP POINTER
ORANGE PUMPKIN CHANNA BUTTER 4 PAPAYA FRUIT 1
PAPAYA CABBAGE 5 TOMATO VEGETABLE 5
PEAS 6 POTATO PULSES 10
7 PUMPKIN MILK 13
8 CABBAGE PRODUCTS
9 PEAS
10 MOONG
11 RAJMA
12 CHANNA
13 CREAM
14 CHEESE
15 BUTTER
RECORDS :
• A record is a collection of relative data items , each of which is called as field or
attribute.
• Collection of records is known as files .
• Collection of data is frequently organised into a hierarchy of fields , records and
files.
• A record may contain non- homogeneous data i.e. data items of record need
not to be of same data type.
• In a record, natural ordering of elements is not possible. The elements in record
can be described by level number.
 Name Class Contact details

Roll number First name Middle name Last name Class Div Land line number Mobile number

Record [ 1 ]

Record [ 2 ]

Record [ 3 ]

• To represent record in memory linear arrays are used. 1 Name

2 First name
• One separate array is used for each elementary item of the 2 Middle name
record such as roll number, first name, middle name, last name ,
2 Last time
class, div etc. 1 CLass
• The records are stored in memory using parallel arrays , such 2 Class
that for an index K of all records Roll number [ K], first name [K], 2 Div
middle name [K], last name [K], class [K], div [K] etc. belong to 1 Contact details
the same record in a file. ( The Kth record in the file ). 2 Landline number
2 Mobile number
Linked lists :
A linked list is a linear collection of data elements, called nodes, where the linear order is
maintained with the help of pointers.
Linked list is also called one way list.
One part of the node is the info part , which contains information of the element , while the
other part is link part, which points to the next
INFO 7 LINK
Start
5 1 D 7
5 START INFO
2
3
4 C 1
5 A 9 A B C D E
6 •9 •4 •1 • 7 •0
7 E 0
8
9 B 4
10 LINK ( POINTER TO THE NEXT NODE )
 INFO 7 LINK
Start 5 START
5 1 95 7
2
3 36 74 87 95 123
4 87 1
•9 •4 •1 • 7 •0
5 36 9
6
Avail
8 7 123 0 INFO 7 LINK
To insert an element in Start
8 third position of the list, 5 1 95 7
9 74 4 the content of AVAIL are
2
stored in LINK part of the
10 second node and LINK part 3
of the second node is 4 87 1
5 START
transferred to LINK part of
5 36 9
new node
6
Avail
74 82 87 95 123 3 7 123 0
36
•9 •8 •4 •1 • 7 •0 8 82 4
9 74 8
10
 INFO 7 LINK 5 START
Start
5 1 95 7
2 36 74 87 95 123
3 •9 •4 •1 • 7 •0
4 87 1
5 36 9
6
Avail To delete a node from
8 7 123 0 INFO 7 LINK
a linked list, the LINK Start
8 part of that node is 5 1 95 7
9 74 4 given to the LINK part 2
10 of the previous node 3
4
5 START
5 36 9
6
Avail
74 95 123 3 7 123 0
36
8
•9 •1 • 7 •0 9 74 1
10
 LIFO FIFO
• LIFO is last in first out system. In this • FIFO is first in first out system. In this
type of system, the element which is type of system, the element which is
inserted at last, will be deleted first. inserted first in the list, will be deleted
• Stack is an example of LIFO system. It first.
is a linear system in which insertion • Queue is an example of FIFO system. It
and deletion takes place only at one is a linear system in which insertion
end i.e. top of the list. takes place only at one end of the list
• The insertion operation is referred to known as ‘rear’ of the list and deletion
as PUSH and deletion operation is takes place at the other end called as
referred to as POP. ‘front’ of the list.
• e.g. Consider a stack of dishes. If we • e.g. a queue for tickets.
want to add a new dish to this stack
then it is added at the top of stack,
deletion also takes place from the top.
 TREE
Tree is a non linear hierarchial data structure which consists of finite set of one or
more nodes LEVEL 0 A
( i.e. collected data items ) such that :
LEVEL 1 B C
• Root : A node which has no parent. Generally
LEVEL 2 D E F G H
first node is called as ‘root node’ . Node A is the
LEVEL 3 I J
root of the tree.
• Leaf :The node which has no child or children. Such nodes have degree zero. In
figure a D, F, H, I, J are the leaf nodes. Also called terminal node.
• Child : The nodes which are reachable from a node. The children of node B are D
and E.
• Sibling : Children of the same parent are said to be siblings . E.g. the nodes F, G
and H are siblings.
• Level of a tree: Each node in a tree is assigned a level number. Generally the
level number of the root of a tree is zero and every other node is assigned a
level number which is one more than the level number of its parent. It is the
distance from the root.
• Depth / height: It is defined as maximum level of any node in a tree. If root is
level 0 then depth or height of tree is equal to 1+ largest level number. Depth of
the tree shown is 3.
• Degree: The number of subtrees of a node is called degree of a node. The
degree of a tree is the maximum degree of the node in a tree. The degree of
each node of the tree is shown in the table. The degree of the tree is 3.
NODE DEGREE LEVEL 0 A
A 2
LEVEL 1 B C
B 2
C 3 LEVEL 2 D E F G H
E 1
LEVEL 3 I J
G 1
D, F, H, I, J 0
BINARY TREE
• Binary tree has a finite set of elements called nodes such that :
1. It may be empty or
2. It is partitioned into three disjoint subsets
a) There is a single distinguished element called the root of the tree. ( A )
b) Other two subsets are themselves a binary tree called left subtree and right
subtree of the original tree. ( B and C )
A left and right subtree may be empty. In binary tree, there is no node with degree
greater than 2.
A

B C

D E F G

H I J
BINARY TREE : BASIC TERMINOLOGY
• Left successor: B is the left successor of node A
• Right successor: C is the right successor of node A
• Left subtree: Left subtree consists of node B, D, E, H
• Right subtree: Right subtree consists of C, F, G ,I ,J
• Terminal node: The nodes with no successors are called terminal nodes. E, G, H, I
and J are called terminal nodes.
• Binary tree T1 and T2 are similar if they have the same structure.
• Any node N in a binary tree has 0, 1 or 2 successors.
A
• Depth of a tree means maximum level of any node in a tree.
• Maximum number of nodes in a binary tree with B C
depth n is 2n – 1.
D E F G
In the given tree structure depth is 4
Hence total number of nodes = 2n – 1 = 24 – 1 = 16 – 1 =15 H I J
• Complete binary tree: if all leaf nodes of a binary tree have same level number
and every non leaf node has non empty left and right subtrees then the tree is
called as complete binary tree.
• Extended binary tree or 2 – tree: A binary tree T is said to be a 2 – tree or an
extended binary tree if each node N has 0 or 2 children. The nodes with 2
children are called internal nodes and the nodes with 0 children are called
external nodes.
• Binary search tree: It is a binary tree in which each node N of the tree has the
property that the value at N is greater than every node value in the left subtree
of N and is less than or equal to every node value in the right subtree of N
14
A
A
B C 4 15
B C
D E 3 9 12 18
D E F G
F G
7
 INFO LEFT RIGHT
Binary tree can be represented in memory in two ways: 1 B 7 14
1. Linked representation ROOT 5 2 4
3 F 0 0
2. Sequential representation AVAIL 10
* A * 4 13
Linked representation. 5 A 1 9

* C * 6 I 0 0
* B *
7 D 0 0
8 H 0 0
X D X E X X F X * G *
9 C 3 11
10 2
X H X X I X X J X 11 G 6 12
Linked representation uses three parallel arrays INFO, LEFT and RIGHT and two 12 J 0 0
variables ROOT and AVAIL such that for an index K , INFO[K] contains actual element, 13 0
LEFT [K] contains address of left child and RIGHT [K] contains address of right child.
14 E 8 0
ROOT stores address of first node of the tree.
AVAIL stores address of first null node . It is used to add a node to the tree.
In the given example to add an element K, AVAIL is used . Hence K will be added at
location INFO[10] . LEFT[10] and RIGHT[10] wil contain zero and AVAIL will contain 2
i.e. the next element is to be added at 2
• Sequential representation:
For sequential representation only one array is used.
INFO
This array is generally known as TREE such that : 1 A
a) The root of the tree is stored in TREE[1] 2 B

b) If a node N of the tree is stored in TREE[K], then, its left successor 3 C

4 D
is stored in TREE[2*K] and right successor is stored in TREE[(2*K)+1]. 5 E
In general, sequential representation of a tree with depth d will require 6 F
7 G
an array with approximately * A * 8 -
2d+1 elements. 9 -
* B * * C * 10 H
11 -

* E X X F X 12 -
X D X * G *
13 -
14 I
X H X X I X X J X 15 J
Representing equations as a binary tree:
E=(a+b)/[(c*d)–e]
=

E /

+ -

a b * e

c d
Representing equations as a binary tree:
[ ( a + b ) * c ] / [ a * (( b – c ) + a )]
/

* *

+ c a +

a b - a

b c
Representing equations as a binary tree:
(2x+y)(a–7b)3
*

+
↑

* y 3
-

2 x a *

7 b
Representing equations as a binary tree
Z=(A+B/E)*(C+D/F)

Z *

+
+

/ /
A C

B E
D F