TREES-CO3

1)HEAP SORT(BINARY HEAP) CODE

2)BST(ALL FUNCTIONS INSERTING,DELETING,INCLUDING
MAX.MIN,SEARCH ETC)
3)AVL TREE CONSTRUCTION AND ROTATIONS AND CODE
4)SPLAY TREE
5) B-TREE
6)REDBLACK TREE
7) EXPRESSION TREE.
HASHING
1)HASHING AND HASHING METHODS(4 TYPES) AND CODE FOR
DIVISION METHOD AND MIDSQUARE METHOD ONLY
.2)COLLISION RESOLUTION
TECHNIQUES(LINEAR,QUADRATIC,SEPERATE CHAINING) CODE FOR
ALL 3 METHODS(UISNG ARRAYS).
3)DOUBLE HASHING
4) REHASHING
5) EXTENSIBLE HASHING
CO-4 GRAPHS
1) DEF AND TERMINOLOGY
2) REPRESENTATION
3)TRANSITIVE CLOSURE
4) TRAVERSALS(BFS,DFS) ALGORITHM AND EXAMPLE
5) MST
6) PRIMS AND KRUSHKALS(ALGORITHMS AND EXAMPLES)

A tree data structure is a hierarchical structure that is used to represent and

organize data in a way that is easy to navigate and search.
 It is a collection of nodes that are connected by edges and has a
hierarchical relationship between the nodes.
  The topmost node of the tree is called the root, and the nodes below it
are called the child nodes.
 Each node can have multiple child nodes, and these child nodes can
also have their own child nodes.

*Binary Tree
The Binary tree means that the node can have maximum two children. Here, binary
name itself suggests that 'two'; therefore, each node can have either 0, 1 or 2
children.

Let's understand the binary tree through an example.

Properties of Binary Tree

o At each level of i, the maximum number of nodes is 2 i.

o The height of the tree is defined as the longest path from the root node to the
leaf node. The tree which is shown above has a height equal to 3. Therefore,
the maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. In
general, the maximum number of nodes possible at height h is (2 0 + 21 + 22+
….2h) = 2h+1 -1.
o The minimum number of nodes possible at height h is equal to h+1.
 o If the number of nodes is minimum, then the height of the tree would be
maximum. Conversely, if the number of nodes is maximum, then the height of
the tree would be minimum.

If there are 'n' number of nodes in the binary tree.

The minimum height can be computed as:

As we know that,

n = 2h+1 -1

n+1 = 2h+1

Taking log on both the sides,

log2(n+1) = log2(2h+1)

log2(n+1) = h+1

h = log2(n+1) - 1

The maximum height can be computed as:

As we know that,

n = h+1

h= n-1

Types of Binary Tree

There are four types of Binary tree:

o Full/ proper/ strict Binary tree

o Complete Binary tree
o Perfect Binary tree
o Degenerate Binary tree
o Balanced Binary tree

1. Full/ proper/ strict Binary tree

The full binary tree is also known as a strict binary tree. The tree can only be
considered as the full binary tree if each node must contain either 0 or 2 children.
The full binary tree can also be defined as the tree in which each node must contain
2 children except the leaf nodes.

Let's look at the simple example of the Full Binary tree.

In the above tree, we can observe that each node is either containing zero or two
children; therefore, it is a Full Binary tree.

Properties of Full Binary Tree

o The number of leaf nodes is equal to the number of internal nodes plus 1. In the
above example, the number of internal nodes is 5; therefore, the number of leaf
nodes is equal to 6.
o The maximum number of nodes is the same as the number of nodes in the binary
tree, i.e., 2h+1 -1.
o The minimum number of nodes in the full binary tree is 2*h-1.
o The minimum height of the full binary tree is log2(n+1) - 1.
o The maximum height of the full binary tree can be computed as:

n= 2*h - 1

n+1 = 2*h

h = n+1/2
Complete Binary Tree

The complete binary tree is a tree in which all the nodes are completely filled except
the last level. In the last level, all the nodes must be as left as possible. In a complete
binary tree, the nodes should be added from the left.

Let's create a complete binary tree.

The above tree is a complete binary tree because all the nodes are completely filled,
and all the nodes in the last level are added at the left first.

Properties of Complete Binary Tree

o The maximum number of nodes in complete binary tree is 2h+1 - 1.

o The minimum number of nodes in complete binary tree is 2h.
o The minimum height of a complete binary tree is log2(n+1) - 1.
o The maximum height of a complete binary tree is

Perfect Binary Tree

A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf
nodes are at the same level.
Let's look at a simple example of a perfect binary tree.

The below tree is not a perfect binary tree because all the leaf nodes are not at the
same level.
Note: All the perfect binary trees are the complete binary trees as well as the full
binary tree, but vice versa is not true, i.e., all complete binary trees and full binary
trees are the perfect binary trees.

Degenerate Binary Tree

The degenerate binary tree is a tree in which all the internal nodes have only one
children.

Let's understand the Degenerate binary tree through examples.

The above tree is a degenerate binary tree because all the nodes have only one child.
It is also known as a right-skewed tree as all the nodes have a right child only.
The above tree is also a degenerate binary tree because all the nodes have only one
child. It is also known as a left-skewed tree as all the nodes have a left child only.

Balanced Binary Tree

The balanced binary tree is a tree in which both the left and right trees differ by
atmost 1. For example, AVL and Red-Black trees are balanced binary tree.

Let's understand the balanced binary tree through examples.

The above tree is a balanced binary tree because the difference between the left
subtree and right subtree is zero.

The above tree is not a balanced binary tree because the difference between the left
subtree and the right subtree is greater than 1.
Binary Tree Implementation
A Binary tree is implemented with the help of pointers. The first node in the tree is
represented by the root pointer. Each node in the tree consists of three parts, i.e.,
data, left pointer and right pointer. To create a binary tree, we first need to create the
node. We will create the node of user-defined as shown below:

1. struct node  
2. {  
3.    int data,  
4.    struct node *left, *right;  
5. }  

In the above structure, data is the value, left pointer contains the address of the left
node, and right pointer contains the address of the right node.

Binary Tree program in C

1. #include<stdio.h>  
2.       struct node  
3.      {  
4.           int data;  
5.           struct node *left, *right;  
6.       }  
7.       void main()  
8.     {  
9.        struct node *root;  
10.        root = create();  
11.     }  
12. struct node *create()  
13. {  
14.    struct node *temp;  
15.    int data;  
16.    temp = (struct node *)malloc(sizeof(struct node));  
17.    printf("Press 0 to exit");  
18.    printf("\nPress 1 for new node");  
19.    printf("Enter your choice : ");  
20.    scanf("%d", &choice);   
21.    if(choice==0)  
 22. {  
23. return 0;  
24. }  
25. else  
26. {  
27.    printf("Enter the data:");  
28.    scanf("%d", &data);  
29.    temp->data = data;  
30.    printf("Enter the left child of %d", data);  
31.    temp->left = create();  
32. printf("Enter the right child of %d", data);  
33. temp->right = create();  
34. return temp;   
35. }  
36. }  

The above code is calling the create() function recursively and creating new node on
each recursive call. When all the nodes are created, then it forms a binary tree
structure. The process of visiting the nodes is known as tree traversal. There are three
types traversals used to visit a node:

o Inorder traversal
o Preorder traversal
o Postorder traversal
#include <stdio.h>

#include <stdlib.h>

struct node {

int data; //node will store some data

struct node *right_child; // right child

struct node *left_child; // left child

};

//function to create a node

struct node* new_node(int x) {

struct node *temp;

temp = malloc(sizeof(struct node));

temp -> data = x;

temp -> left_child = NULL;

temp -> right_child = NULL;

return temp;

// searching operation

struct node* search(struct node * root, int x)

{
 if (root == NULL || root -> data == x) //if root->data is x then the element is found

return root;

else if (x > root -> data) // x is greater, so we will search the right subtree

return search(root -> right_child, x);

else //x is smaller than the data, so we will search the left subtree

return search(root -> left_child, x);

// insertion

struct node* insert(struct node * root, int x)

//searching for the place to insert

if (root == NULL)

return new_node(x);

else if (x > root -> data) // x is greater. Should be inserted to the right

root -> right_child = insert(root -> right_child, x);

else // x is smaller and should be inserted to left

root -> left_child = insert(root -> left_child, x);

return root;

//function to find the minimum value in a node

struct node* find_minimum(struct node * root) {

 if (root == NULL)

return NULL;

else if (root -> left_child != NULL) // node with minimum value will have no left child

return find_minimum(root -> left_child); // left most element will be minimum

return root;

// deletion

struct node* delete(struct node * root, int x) {

//searching for the item to be deleted

if (root == NULL)

return NULL;

if (x > root -> data)

root -> right_child = delete(root -> right_child, x);

else if (x < root -> data)

root -> left_child = delete(root -> left_child, x);

else {

//No Child node

if (root -> left_child == NULL && root -> right_child == NULL) {

free(root);

return NULL;

}
 //One Child node

else if (root -> left_child == NULL || root -> right_child == NULL) {

struct node *temp;

if (root -> left_child == NULL)

temp = root -> right_child;

else

temp = root -> left_child;

free(root);

return temp;

//Two Children

else {

struct node *temp = find_minimum(root -> right_child);

root -> data = temp -> data;

root -> right_child = delete(root -> right_child, temp -> data);

return root;

// Inorder Traversal

void inorder(struct node *root) {

 if (root != NULL) // checking if the root is not null

inorder(root -> left_child); // traversing left child

printf(" %d ", root -> data); // printing data at root

inorder(root -> right_child); // traversing right child

int main() {

struct node *root;

root = new_node(20);

insert(root, 5);

insert(root, 1);

insert(root, 15);

insert(root, 9);

insert(root, 7);

insert(root, 12);

insert(root, 30);

insert(root, 25);

insert(root, 40);

insert(root, 45);

insert(root, 42);

inorder(root);
 printf("\n");

root = delete(root, 1);

root = delete(root, 40);

root = delete(root, 45);

root = delete(root, 9);

inorder(root);

printf("\n");

return 0;