Binary Trees

A binary tree is a tree in which every node has at most two children.

Full Binary Tree → A binary tree in which every node has 2 children except the leaves is
known as a full binary tree.
Complete Binary Tree → A binary tree which is completely filled with a possible exception at
the bottom level i.e.,
• the last level may not be completely filled and the bottom level is filled from left to right.

the difference between a full and a complete

binary tree.
The parent of node i
The left child of node i is 2i
The right child of node i is 2i+1
Perfect Binary Tree → In a perfect binary tree, each leaf is at the same level and all the
interior nodes have two children.

Thus, a perfect binary tree will have the

maximum number of nodes for all alternative
binary trees of the same height and it will be
2h+1 – 1 which we are going to prove next.
Maximum Number of Nodes in a Binary Tree

We know that the maximum number of nodes will be in a perfect binary tree. So, let's
assume that the height of a perfect binary tree is h.
• Degree: The degree of a node of a tree is defined as the number of children of that node.
• All the internal nodes have a degree of 2.
• The leaf nodes of a perfect binary tree have a degree of 0.
• Number of nodes at level 0 = 20 = 1
• Number of nodes at level 1 = 21 = 2
• then the number of leaf nodes will be 2h
• total number of nodes can be calculated as 20 + 21 + . . . + 2h = 2h+1 – 1
• height of a perfect binary tree with N number of nodes = log(N + 1) – 1 = Θ(ln(n)).
• Depth of a node: Average depth of a node in a perfect binary tree is Θ(ln(n)).
• This can be calculated using the relation shown while calculating the total number of
nodes in a perfect binary tree.
• In a perfect binary tree, the number of nodes at each level should be a power of 2 (e.g. 1,
2, 4, 8, etc.).
• If any level has a different number of nodes, the tree is not a perfect binary tree.
Array Representation of Binary Tree: We start by numbering the nodes of the tree
from 1 to n(number of nodes).
 For the linked representation, we can easily access the parent, right child and the left child
with T.parent, T.right and T.left respectively.

RIGHT_CHILD(index) LEFT_CHILD(index)
if (T[index] != null and (2*index + 1) <= T.size) if (T[index] != null and (2*index) <= T.size)
return (2*index + 1) return (2*index)
else else
return null return null

PARENT(index)
if (T[index] != null and (floor(index/2)) =! null)
return floor(index/2)
else
return null
Applications of Binary tree
• Binary trees are used to represent a nonlinear data structure.
• There are various forms of Binary trees.
• Binary trees play a vital role in a software application.
• One of the most important applications of the Binary tree is in the searching algorithm.
• The tree contains the root element.
• T1, T2, T3, T4 …. Tn which are called subtrees.

Binary Tree Traversal

1. Pre order Traversal
2. Post order Traversal
3. In order Traversal

PREORDER(n)
if(n != null)
print(n.data) // visiting root PREORDER(n.left)
// visiting left subtree
PREORDER(n.right) // visiting right subtree
POSTORDER(n)
if(n != null)
PREORDER(n.left) // visiting left subtree
PREORDER(n.right) // visiting right subtree
print(n.data) // visiting root

INORDER(n)
if(n != null) INORDER(n.left)
print(n.data)
INORDER(n.right)
Binary Search Tree is a binary tree in which every node contains only smaller values in
its left sub tree and only larger values in its right sub tree.

Every binary search tree is a binary tree but

every binary tree need not to be binary
search tree.
The following tree is a Binary Search Tree.
• In this tree, left subtree of every node contains nodes with smaller values
• right subtree of every node contains larger values.
• Every binary search tree is a binary tree
• Every binary tree need not to be binary search tree.

Operations on a Binary Search Tree:

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

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.

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.

Step 4 - If the tree is Not Empty, then check if the value of newNode is smaller or larger

Step 5 - If new Node is smaller than or equal to the node then move to its left child. If new

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

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

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.

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

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.
Construct a Binary Search Tree by inserting the following sequence of numbers...
10,12,5,4,20,8,7,15 and 13
Delete 4,20,8,7,15
B-tree
• B-tree is a special type of self-balancing search tree in which each node can contain more
than one key and can have more than two children.
• It is a generalized form of the binary search tree.
• It is also known as a height-balanced m-way tree.
Why do you need a B-tree data structure?

• The need for B-tree arose with the rise in the need for lesser time in accessing physical

storage media like a hard disk.

• The secondary storage devices are slower with a larger capacity.

• There was a need for such types of data structures that minimize the disk access.

• Other data structures such as a binary search tree, avl tree, red-black tree, etc can

store only one key in one node.

• If you have to store a large number of keys, then the height of such trees becomes very

large, and the access time increases.

• However, B-tree can store many keys in a single node and can have multiple child

nodes.

• This decreases the height significantly allowing faster disk accesses.

B-tree Properties
1. For each node x, the keys are stored in increasing order.
2. In each node, there is a boolean value x.leaf which is true if x is a leaf.
3. If n is the order of the tree, each internal node can contain at most n - 1 keys along with a
pointer to each child.

4. Each node except root can have at most n children and at least n/2 children.

5. All leaves have the same depth (i.e. height-h of the tree).

6. The root has at least 2 children and contains a minimum of 1 key.

7. If n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2, h ≥ logt (n+1)/2.

Operations on a B-tree
• Searching an element in a B-tree
• Searching for an element in a B-tree is the generalized form of searching an element in a
Binary Search
• Tree. The following steps are followed.
Starting from the root node, compare k with the first key of the node.
If k = the first key of the node, return the node and the index.
2. If k.leaf = true, return NULL (i.e. not found).
3. If k < the first key of the root node, search the left child of this key recursively.
4. If there is more than one key in the current node and k > the first key, compare k with
the next key in the node.
If k < next key, search the left child of this key (ie. k lies in between the first and the second
keys).
Else, search the right child of the key.
5. Repeat steps 1 to 4 until the leaf is reached.
Algorithm for Searching an Element:
BtreeSearch(x, k)
i=1
while i ≤ n[x] and k ≥ keyi[x] // n[x] means number of keys in x node
do i = i + 1
if i ≤ n[x] and k = keyi[x]
then return (x, i)
if leaf [x]
then return NIL
else
return BtreeSearch(ci[x], k)

Inserting an element on a B-tree consists of two events: searching the appropriate node
to insert the element and splitting the node if required.
Insertion operation always takes place in the bottom-up
approach.
Let us understand these events below.
Insertion Operation
1. If the tree is empty, allocate a root node and insert the key.
2. Update the allowed number of keys in the node.
3. Search the appropriate node for insertion.
4. If the node is full, follow the steps below.
5. Insert the elements in increasing order.
6. Now, there are elements greater than its limit. So, split at the median.
7. Push the median key upwards and make the left keys as a left child and the right keys as a
right child.
8. If the node is not full, follow the steps below.
9. Insert the node in increasing order.
Insertion Example
Let us understand the insertion operation with the illustrations below.
The elements to be inserted are 8, 9, 10, 11, 15, 20, 17.
Insertion into a B-tree:
Inserting an element on a B-tree consists of two events:
searching the appropriate node to insert the element and splitting the node if required.
Insertion operation always takes place in the bottom-up approach.
Let us understand these events below.
Insertion Operation
1. If the tree is empty, allocate a root node and insert the key.
2. Update the allowed number of keys in the node.
3. Search the appropriate node for insertion.
4. If the node is full, follow the steps below.
5. Insert the elements in increasing order.
6. Now, there are elements greater than its limit. So, split at the median.
7. Push the median key upwards and make the left keys as a left child and the right keys as a
right child.
8. If the node is not full, follow the steps below.
9. Insert the node in increasing order.
Insertion Example
• Let us understand the insertion operation with the illustrations below.
• The elements to be inserted are 8, 9, 10, 11, 15, 20, 17.
Deletion from a B-tree:

Deleting an element on a B-tree consists of three main events: searching the node where

the key to be deleted exists,

deleting the key and balancing the tree if required.

While deleting a tree, a condition called underflow may occur.

Underflow occurs when a node contains less than the minimum number of keys it should

hold.

The terms to be understood before studying deletion operation are:

1. Inorder Predecessor

The largest key on the left child of a node is called its inorder predecessor.

2. Inorder Successor

The smallest key on the right child of a node is called its inorder successor.
Before going through the steps below, one must know these facts about a B tree of degree m.
1. A node can have a maximum of m children. (i.e. 3)
2. A node can contain a maximum of m - 1 keys. (i.e. 2)
3. A node should have a minimum of ⌈m/2⌉ children. (i.e. 2)
4. A node (except root node) should contain a minimum of ⌈m/2 ⌉ - 1 keys. (i.e. 1)
There are three main cases for deletion operation in a B tree.
Case I
The key to be deleted lies in the leaf. There are two cases for it.
• The deletion of the key violates the property of the minimum number of keys a node
should hold.
• In this case, we borrow a key from its immediate neighboring sibling node in the order of
left to right.

• 2. Del 30
Case II
• If the key to be deleted lies in the internal node, the following cases occur.
1. The internal node, which is deleted, is replaced by an inorder predecessor if the left child
has more than the minimum

• 2. Del 30
Case III
• In this case, the height of the tree shrinks.
• If the target key lies in an internal node, and the deletion of the key leads to a fewer
number of keys in the node (i.e. less than the minimum required), then look for the inorder
predecessor and the inorder successor.
• If both the children contain a minimum number of keys then, borrowing cannot take place.
• This leads to Case II(3) i.e. merging the children.