TREES

TREE - TERMINOLOGY

Tree is a non-linear data structure which organizes data in hierarchical structure and this is a

recursive definition.
 Terminology

In a tree data structure, we use the following terminology...

1. Root
In a tree data structure, the first node is called as Root Node.
2. Edge
In a tree data structure, the connecting link between any two nodes is
called as EDGE.
3. Parent

In a tree data structure, the node which is a predecessor of any node is

called as PARENT NODE.
4. Child

In a tree data structure, the node which is descendant of any node

is called as CHILD Node.
5. Siblings

In a tree data structure, nodes which belong to same Parent are called
as SIBLINGS. In simple, words, the nodes with the same parent are
called Sibling nodes.
6. Leaf
In a tree data structure, the node which does not have a child is called as
LEAF Node.
7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as
INTERNAL Node
8. Degree
In a tree data structure, the total number of children of a node is called as
DEGREE of that Node.
9. Level

In a tree data structure, 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...
10. Height
In a tree data structure, the total number of edges from leaf node to a particular
node in the longest path is called as HEIGHT of that Node.
11. Depth

In a tree data structure, the total number of egdes from root node to a
particular node is called as DEPTH of that Node.
12. Path

In a tree data structure, the sequence of Nodes and Edges from one node
to another node is called as PATH between that two Nodes.
13. Sub Tree

In a tree data structure, each child from a node forms a subtree recursively.
Every child node will form a subtree on its parent node.
BINARY TREES
BINARY TREE TYPES

1. Extended Binary Tree

2. Complete Binary Tree
3. Full Binary Tree
4. Skewed Binary Tree
5. Strictly Binary Tree
6. Expression Binary tree
EXTENDED BINARY TREE

An extended binary tree is a transformation of any binary tree into a completebinary

tree. This transformation consists of replacing every null subtree of the
original tree with “special nodes”or “failure nodes” .The nodes from the
original tree are then internal nodes, while the “special nodes” are external nodes.
 COMPLETE BINARY TREE

A complete binary tree is a tree in which

[Link] leaf nodes are at n or n-1 level
[Link] are filled from left to right
FULL BINARY TREE

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node
other than the leaves has two children or no childeren. Every level is completely filled up.
No of nodes= 2h+1 -1
SKEWED BINARY TREE
A binary tree is said to be Skewed Binary Tree if every node in the tree contains either
only left or only right sub tree. If the node contains only left sub tree then it is
called left-skewed binary tree and if the tree contains only right sub tree then it is
called right-skewed binary tree.
STRICTLY BINARY TREE

A node will have either two

children or no child at all.
EXPRESSION BINARY TREE

• Expression trees are a special kind of binary tree used to evaluate certain expressions.
• Two common types of expressions that a binary expression tree can represent are algebraic
and boolean.
• These trees can represent expressions that contain both unary and binary operators.
• The leaves of a binary expression tree are operands, such as constants or variable names, and
the other nodes contain operators.
• Expression tree are used in most compilers.
Expression Binary tree
Binary Tree Representations
 BINARY TREE REPRESENTATIONS
A binary tree data structure is represented using two
methods. Those methods are as follows...
[Link] Representation
[Link] List Representation

1. Array Representation of Binary Tree

In array representation of a binary tree, we use one-dimensional array
(1-D Array) to represent a binary tree.
Consider the above example of a binary tree and it is represented as
follows...

To represent a binary tree of depth 'n' using array representation, we need one
dimensional array with a maximum size of 2n + 1.
2. Linked List Representation of Binary Tree
We use a double linked list to represent a binary tree. In a double linked list, every node consists of
three fields. First field for storing left child address, second for storing actual data and third for storing
right child address.
In this linked list representation, a node has the following structure...

The above example of the binary tree represented using Linked list representation is shown as follows...
BINARY TREE TRAVERSALS
 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.
[Link] - Order Traversal
[Link] - Order Traversal
[Link] - Order Traversal

Consider the following binary tree...

[Link] - Order Traversal ( leftChild - root - rightChild )
In In-Order traversal, the root node is visited between the left child and right child.
In this traversal,
✓the left child node is visited first,
✓then the root node is visited
✓and later we go for visiting the right child node.
This in-order traversal is applicable for every root node of all subtrees in the tree. This is performed
recursively for all nodes in the tree.

In-Order Traversal for above example of binary tree is

I-D-J-B-F-A-G-K-C–H

}
/* Given a binary tree, print its nodes in inorder*/

void Inorder(struct node* node)

{
if (node == NULL) return;
/* first recur on left child */
Inorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
Inorder(node->right);
}
[Link] - Order Traversal ( root - leftChild - rightChild )
In Pre-Order traversal, the root node is visited before the
left child and right child nodes.
In this traversal,
✓the root node is visited first,
✓then its left child
✓and later its right child.
This pre-order traversal is applicable for every root node
of all subtrees in the tree.

Pre-Order Traversal for above example binary tree is

A-B-D -I-J-F-C-G-K–H
}
/* Given a binary tree, print its nodes in preorder*/
void Preorder(struct node* node)
{
if (node == NULL) return;
/* first print data of node */
printf("%d ", node->data);
/* then recur on left sutree */
Preorder(node->left);
/* now recur on right subtree */
Preorder(node->right);
}
[Link] - Order Traversal ( leftChild - rightChild -
root )
In Post-Order traversal, the root node is visited after
left child and right child.
In this traversal,
✓left child node is visited first,
✓then its right child
✓and then its root node.
This is recursively performed until the right most
node is visited.
Post-Order Traversal for above example
binary tree is

I-J-D-F-B-K-G-H–C- A
}
void Postorder(struct node* node)
{
if (node == NULL)
return;

// first recur on left subtree

Postorder(node->left);
// then recur on right subtree
Postorder(node->right);

// now deal with the node

printf("%d ", node->data);

}
BINARY SEARCH TREE
Binary search tree can be defined as follows...
Binary Search Tree is a binary tree in which every node contains only smaller values

in its left subtree and only larger values in its right subtree.

In a binary search tree, all the nodes in the left subtree of any node contains smaller values
and all the nodes in the right subtree of any node contains larger values as shown in the
following figure...
 Example

The following tree is a Binary Search Tree. In this tree, left subtree of every node
contains nodes with smaller values and right subtree of every node contains larger values.

very binary search tree is a binary tree but every binary tree need not to be binary

search tree.
Example

Construct a Binary Search Tree by inserting the following sequence of numbers...

10,12,5,4,20,8,7,15 and 13

Above elements are inserted into a Binary Search Tree as follows...

Construct a Binary Search Tree (BST) for the following sequence of numbers-
50, 70, 60, 20, 90, 10, 40, 100

When elements are given in a sequence,

• Always consider the first element as the root node.

• Consider the given elements and insert them in the BST one by one.
The binary search tree will be constructed as explained below-

Insert 50-

Insert 70-

• As 70 > 50, so insert 70 to the right of 50.

Insert 60-

• As 60 > 50, so insert 60 to the right of 50.

• As 60 < 70, so insert 60 to the left of 70.
Insert 20-

• As 20 < 50, so insert 20 to the left of 50.

Insert 90-

• As 90 > 50, so insert 90 to the right of 50.

• As 90 > 70, so insert 90 to the right of 70.
Insert 10-

• As 10 < 50, so insert 10 to the left of

50.
• As 10 < 20, so insert 10 to the left of
20.

Insert 40-

• As 40 < 50, so insert 40 to the left of 50.

• As 40 > 20, so insert 40 to the right of 20.
Insert 100-

• As 100 > 50, so insert 100 to the right of 50.

• As 100 > 70, so insert 100 to the right of 70.
• As 100 > 90, so insert 100 to the right of 90.
OPERATIONS ON BINARY SEARCH TREES

The following operations are performed on a binary search tree...

1. Search
2. Insertion
3. Deletion
SEARCH OPERATION IN BST

In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation is
performed as follows.

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.
Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function
Step 4 - If both are not matched, then check whether search element is smaller or larger than that node value.
Step 5 - If search element is smaller, then continue the search process in left subtree.
SEARCH OPERATION IN BST

Step 6- If search element is larger, then continue the search process in right subtree.
Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf node
Step 8 - If we reach to the node having the value equal to the search value then display "Element is found" and
terminate the function.
Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display "Element is not
found" and terminate the function.
INSERTION OPERATION IN BST

In a binary search tree, the insertion operation is performed with O(log n) time complexity. In binary
search tree, new node is always inserted as a leaf node. The insertion operation is performed as follows.

Step 1 - Create a newNode with given value and set its left and right to NULL.
Step 2 - Check whether tree is Empty.
Step 3 - If the tree is Empty, then set root to newNode.
INSERTION OPERATION IN BST

Step 4 - If the tree is Not Empty, then check whether the value of newNode is smaller or larger than the node (here
it is root node).
Step 5 - If newNode is smaller than or equal to the node then move to its left child. If newNode is larger than the
node then move to its right child.
Step 6- Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).
Step 7 - After reaching the leaf node, insert the newNode as left child if the newNode is smaller or equal to that leaf
node or else insert it as right child.
DELETION OPERATION IN BST

 In a binary search tree, the deletion operation is performed with O(log n) time
complexity. Deleting a node from Binary search tree includes following three cases.

Case 1: Deleting a Leaf node (A node with no children)

Case 2: Deleting a node with one child
Case 3: Deleting a node with two children
DELETION OPERATION IN BST

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST

Step 1 - Find the node to be deleted using search operation
Step 2 - Delete the node using free function (If it is a leaf) and terminate the function.
DELETION OPERATION IN BST

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...
Step 1 - Find the node to be deleted using search operation
Step 2 - If it has only one child then create a link between its parent node and child
node.
Step 3 - Delete the node using free function and terminate the function.
DELETION OPERATION IN BST

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...
Step 1 - Find the node to be deleted using search operation
Step 2 - If it has two children, then find the largest node in its left subtree (OR)
the smallest node in its right subtree.
Step 3 - Swap both deleting node and node which is found in the above step.
DELETION OPERATION IN BST

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...
Step 4 - Then check whether deleting node came to case 1 or case 2 or else goto step 2
Step 5 - If it comes to case 1, then delete using case 1 logic.
Step 6- If it comes to case 2, then delete using case 2 logic.
Step 7 - Repeat the same process until the node is deleted from the tree.
AVL TREES
AVL TREES
 AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis
and invented 1962.
 AVL tree is a self – balancing binary search tree.
 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.
AVL TREES

 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.

Balance Factor (k) = height (left(k)) - height (right(k))

 If balance factor of any node is 1, it means that the left sub-tree is one level higher than the
right sub-tree.
AVL TREES

 If balance factor of any node is 0, it means that the left sub-tree and right sub-tree
contain equal height.

 If balance factor of any node is -1, it means that the left sub-tree is one level lower
than the right sub-tree.

 An AVL tree is given in the following figure. We can see that, balance factor
associated with each node is in between -1 and +1. therefore, it is an example of
AVL tree.
AVL ROTATIONS

 AVL We perform rotation in AVL tree only in case if Balance Factor is other than -1,
0, and 1.
 There are basically four types of rotations which are as follows:

1. L L rotation: Inserted node is in the left subtree of left subtree of A

2. R R rotation : Inserted node is in the right subtree of right subtree of A
3. L R rotation : Inserted node is in the right subtree of left subtree of A
4. R L rotation : Inserted node is in the left subtree of right subtree of A
1. RR ROTATION
When BST becomes unbalanced, due to a node is inserted into the right subtree of the right subtree of A,
then we perform RR rotation, RR rotation is an anticlockwise rotation, which is applied on the edge below
a node having balance factor -2

In above example, node A has balance factor -2 because a node C is inserted in the right subtree of A right subtree.
We perform the RR rotation on the edge below A.
2. LL ROTATION

 When BST becomes unbalanced, due to a node is inserted into the left subtree of the
left subtree of C, then we perform LL rotation, LL rotation is clockwise rotation,
which is applied on the edge below a node having balance factor 2.

In above example, node C has balance factor 2 because a node A is inserted in the
left subtree of C left subtree. We perform the LL rotation on the edge below A.
3. LR ROTATION

 LR rotation = RR rotation + LL rotation, i.e.,

 first RR rotation is performed on subtree and
 then LL rotation is performed on full tree, by full tree we mean the
first node from the path of inserted node whose balance factor is
other than -1, 0, or 1.
State Action

A node has been inserted into the right subtree of the left subtree.
This makes C an unbalanced node. These scenarios cause AVL tree
to perform left-right rotation.

We first perform the left rotation on the left subtree of C. This

makes A, the left subtree of B.

Node C is still unbalanced, however now, it is because of the left-

subtree of the left-subtree.

We shall now right-rotate the tree, making B the new root node
of this subtree. C now becomes the right subtree of its own left
subtree.

Tree is balanced now

R L ROTATION

 R L rotation = LL rotation + RR rotation, i.e.,

 first LL rotation is performed on subtree and
 then RR rotation is performed on full tree, by full tree we mean the first node from
the path of inserted node whose balance factor is other than -1, 0, or 1.
State Action

A node has been inserted into the left subtree of the right
subtree. This makes A, an unbalanced node with balance factor
2.

First, we perform the right rotation along C node,

making C the right subtree of its own left subtree B.
Now, B becomes the right subtree of A.

Node A is still unbalanced because of the right subtree of its

right subtree and requires a left rotation.

A left rotation is performed by making B the new root node of

the subtree. A becomes the left subtree of its right subtree B.

The tree is now balanced.

OPERATIONS ON AN AVL TREE

 The following operations are performed on AVL tree...

 Search
 Insertion
 Deletion
SEARCH OPERATION IN AVL TREE

Step 5 - If search element is smaller, then continue the search process in left subtree.
Step 6 - If search element is larger, then continue the search process in right subtree.
Step 7 - Repeat the same until we find the exact element or until the search element is compared with
the leaf node.
Step 8 - If we reach to the node having the value equal to the search value, then display "Element is
found" and terminate the function.
Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display
"Element is not found" and terminate the function.
SEARCH OPERATION IN AVL TREE

In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation in the AVL tree is similar to the search
operation in a Binary search tree. We use the following steps to search an element in AVL tree...
Step 1 - Read the search element from the user.
Step 2 - Compare the search element with the value of root node in the tree.
Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function
Step 4 - If both are not matched, then check whether search element is smaller or larger than that node value.
Step 5 - If search element is smaller, then continue the search process in left subtree.
Step 6 - If search element is larger, then continue the search process in right subtree.
Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf node.
Step 8 - If we reach to the node having the value equal to the search value, then display "Element is found" and terminate the function.
Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display "Element is not found" and terminate
the function.
HUFFMAN ENCODING TREE

 Huffman Coding is a technique of compressing data to reduce its size without losing
any of the details. It was first developed by David Huffman.
 Huffman Coding is generally useful to compress the data in which there are frequently
occurring characters.
HUFFMAN ENCODING TREE

Suppose the string below is to be sent over a network.

Each character occupies 8 bits. There are a total of 15 characters in the above string.
Thus, a total of 8 * 15 = 120 bits are required to send this string.
 HUFFMAN ENCODING TREE
Huffman coding is done with the help of the following steps.
[Link] the frequency of each character in the string.

2. Sort the characters in increasing order of the frequency. These are stored in
a priority queue Q. Characters sorted according to the frequency

[Link] each unique character as a leaf node.

 HUFFMAN ENCODING TREE

4. Create an empty node z. Assign the minimum frequency to the left child of
z and assign the second minimum frequency to the right child of z. Set the
value of the z as the sum of the above two minimum frequencies.
HUFFMAN ENCODING TREE

5. Remove these two minimum frequencies from Q and add the sum into
the list of frequencies (* denote the internal nodes in the figure above).
6. Insert node z into the tree.
7. Repeat steps 3 to 5 for all the characters.
HUFFMAN ENCODING TREE

Repeat steps 3 to 5 for all the characters.

HUFFMAN ENCODING TREE

 For each non-leaf node, assign 0 to the left edge and 1 to the right edge.
HUFFMAN ENCODING TREE

Character Frequency Code Size

A 5 11 5*2 = 10

B 1 100 1*3 = 3

C 6 0 6*1 = 6

D 3 101 3*3 = 9

4 * 8 = 32 bits 15 bits 28 bits

Without encoding, the total size of the string was 120 bits.
After encoding the size is reduced to 32 + 15 + 28 = 75
B-TREE AND B+ TREE
 B TREES

➢ B Tree is a specialized m-way tree that can be widely used for disk access.

➢ A B-Tree of order m can have at most m-1 keys and m children.

➢ One of the main reason of using B tree is its capability to store large number of keys
in a single node and large key values by keeping the height of the tree relatively small

➢ A B tree of order m contains all the properties of an M way tree.

 B TREES

1. Every node in a B-Tree contains at most m children.

2. Every node in a B-Tree except the root node and the leaf node contain at least m/2
children.

3. The root nodes must have at least 2 nodes.

4. All leaf nodes must be at the same level. It is not necessary that, all the nodes contain
the same number of children but, each node must have m/2 number of nodes.
 OPERATIONS : SEARCHING :

 Searching in B Trees is similar to that in Binary search tree. For example, if we search
for an item 49 in the following B Tree. The process will something like following :

1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.

1. Since, 40<49<56, traverse right sub-tree of 40.

2. 49>45, move to right. Compare 49 match found, return Searching in a B tree depends
upon the height of the tree. The search algorithm takes O(log n) time to search any
element in a B tree.
INSERTING

 Insertions are done at the leaf node level. The following algorithm needs
to be followed in order to insert an item into B Tree.

1. Traverse the B Tree in order to find the appropriate leaf node at which the
node can be inserted.

2. If the leaf node contain less than m-1 keys then insert the element in the
increasing order.
INSERTING

▪ Else, if the leaf node contains m-1 keys, then follow the following steps.
1. Insert the new element in the increasing order of elements.
2. Split the node into the two nodes at the median.
3. Push the median element upto its parent node.
4. If the parent node also contain m-1 number of keys, then split it too by
following the same steps.
 Example:
 Insert the node 8 into the B Tree of order 5 shown in the following image.


8 will be inserted to the right of 5, therefore insert 8.

 The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys.
 Therefore split the node from the median i.e. 8 and push it up to its parent node shown as
follows.
DELETION

 Deletion is also performed at the leaf nodes. The node which is to be

deleted can either be a leaf node or an internal node. Following algorithm
needs to be followed in order to delete a node from a B tree.

1. Locate the leaf node.

1. If there are more than m/2 keys in the leaf node then delete the desired
key from the node.
DELETION
▪ If the leaf node doesn't contain m/2 keys then complete the keys by taking the
element from eight or left sibling.

1. If the left sibling contains more than m/2 elements then push its largest
element up to its parent and move the intervening element down to the
node where the key is deleted.

2. If the right sibling contains more than m/2 elements then push its smallest
element up to the parent and move intervening element down to the node
where the key is deleted.
DELETION

▪ If neither of the sibling contain more than m/2 elements then create a new leaf node
by joining two leaf nodes and the intervening element of the parent node.
▪ If parent is left with less than m/2 nodes then, apply the above process on the parent
too.
▪ If the the node which is to be deleted is an internal node, then replace the node with
its in-order successor or predecessor. Since, successor or predecessor will always be
on the leaf node hence, the process will be similar as the node is being deleted from
the leaf node.
 Example 1
 Delete the node 53 from the B Tree of order 5 shown in the following figure.

53 is present in the right child of element 49. Delete it.

➢ Now, 57 is the only element which is left in the node, the minimum number of elements that must
be present in a B tree of order 5, is 2.
➢ it is less than that, the elements in its left and right sub-tree are also not sufficient therefore,
merge it with the left sibling and intervening element of parent i.e. 49.
➢ The final B tree is shown as follows.
APPLICATION OF B TREE

➢ B tree is used to index the data and provides fast access to the actual data stored
on the disks since, the access to value stored in a large database that is stored on
a disk is a very time consuming process.

➢ Searching an un-indexed and unsorted database containing n key values needs

O(n) running time in worst case.

➢ However, if we use B Tree to index this database, it will be searched in O(log n)

time in worst case.
B+ TREES
➢ A B+ tree is an advanced form of a self-balancing tree in which all the values
are present in the leaf level.

➢ B+ tree is multilevel indexing. In multilevel indexing, the index of indices is

created as in figure below. It makes accessing the data easier and faster.
B+ TREES
 B+ TREES

▪ B+ Tree is an extension of B Tree which allows efficient insertion, deletion and search
operations.

▪ In B Tree, Keys and records both can be stored in the internal as well as leaf nodes.
Whereas, in B+ tree, records (data) can only be stored on the leaf nodes while internal
nodes can only store the key values.

▪ The leaf nodes of a B+ tree are linked together in the form of a singly linked lists to
make the search queries more efficient.
B+ TREES

 B+ Tree are used to store the large amount of data which can
not be stored in the main memory.

 Due to the fact that, size of main memory is always limited, the
internal nodes (keys to access records) of the B+ tree are
stored in the main memory whereas, leaf nodes are stored in
the secondary memory.
B+ TREES
The internal nodes of B+ tree are often called index nodes. A B+ tree of order 3 is shown in the following figure.

INSERTION IN B+ TREE

 Step 1: Insert the new node as a leaf node

 Step 2: If the leaf doesn't have required space, split the node and copy the middle
node to the next index node.

 Step 3: If the index node doesn't have required space, split the node and copy the
middle element to the next index page.
Insert the value 195 into the B+ tree of order 5 shown in the following
figure.
 195 will be inserted in the right sub-tree of 120 after 190. Insert it at
the desired position.

 he node contains greater than the maximum number of elements i.e. 4, therefore split it and place the median
node up to the parent.

The node contains greater than the maximum number of elements i.e. 4, therefore split it
and place the median node up to the parent.
Now, the index node contains 6 children and 5 keys which violates the B+ tree properties
Therefore we need to split it, shown as follows.
DELETION IN B+ TREE

 Step 1: Delete the key and data from the leaves.

 Step 2: if the leaf node contains less than minimum number of elements, merge down
the node with its sibling and delete the key in between them.

 Step 3: if the index node contains less than minimum number of elements, merge the
node with the sibling and move down the key in between them.
 Delete the key 200 from the B+ Tree shown in the following figure.
 200 is present in the right sub-tree of 190, after 195. delete it.
 Merge the two nodes by using 195, 190, 154 and 129.
 Merge the two nodes by using 195, 190, 154 and 129.
 Now, element 120 is the single element present in the node which is violating the B+ Tree properties.
Therefore, we need to merge it by using 60, 78, 108 and 120.

 Now, the height of B+ tree will be decreased by 1.

B+TREES
 B TREES VS B+ TREES

SN B Tree B+ Tree
1 Search keys can not be repeatedly Redundant search keys can be present.
stored.
2 Data can be stored in leaf nodes as Data can only be stored on the leaf
well as internal nodes nodes.
3 Searching for some data is a slower Searching is comparatively faster as data
process since data can be found on can only be found on the leaf nodes.
internal nodes as well as on the leaf
nodes.
B TREES VS B+ TREES

SN B - TREES B + TREES
4 Deletion of internal nodes are so Deletion will never be a complexed process
complicated and time consuming. since element will always be deleted from
the leaf nodes.

5 Leaf nodes can not be linked together. Leaf nodes are linked together to make the
search operations more efficient.