Binary Search Tree.pptxA binary search i

A binary search tree (BST) is a binary tree where every node in the left subtree is less than the root, and every node in the right subtree is of a value greater than the root.

1. Binary Search Tree It is a type of binary tree it means one root node and atleast two child

2. Binary search tree

3. Binary search tree Properties of Binary Search Tree All nodes of the Left -Subtree are lesser than the node itself. All nodes of the Right -Subtree are grater than the node itself. Left and Right Subtree is also binary search trees. There are no duplicate node it means no same value nodes in BST.

4. BST FIG3.

5. BST Above fig This is a binary search tree which can satisfied all properties each of the nodes. Start with Root Nodes element 9. All the nodes of Left subtree [2,4,5,7,8] are smaller than 9 All the nodes of Right subtree [14,15,11] are grater than 9.   InOrder traversal of binary search tree gives an ascending sorted array. Find InOrder Traversal We will start from the root Node, and driven towards the left subtree .

6. TRAVERSAL

7. bst InOrder : 2>4>4>6>7>8>9>11>14>15 Which is increasing sorted Order. Hence it is binary search tree .    

8. Coding part in BST #include<stdio.h> #include<malloc.h> struct node { int data; struct node* left; struct node* right; }; struct node* createNode(int data){ struct node *n; // creating a node pointer n = (struct node *) malloc(sizeof(struct node)); // Allocating memory in the heap n->data = data; // Setting the data n->left = NULL; // Setting the left and right children to NULL n->right = NULL; // Setting the left and right children to NULL return n; // Finally returning the created node }

9. Function in Bst void preOrder(struct node* root){ if(root!=NULL){ printf("%d ", root->data); preOrder(root->left); preOrder(root->right); } } void postOrder(struct node* root){ if(root!=NULL){ postOrder(root->left); postOrder(root->right); printf("%d ", root->data); } } void inOrder(struct node* root){ if(root!=NULL){ inOrder(root->left); printf("%d ", root->data); inOrder(root->right); } }

10. Function is bst int isBST(struct node* root) { static struct node *prev = NULL; // root node does not have any parents if(root!=NULL){ if(!isBST(root->left)){ return 0; } if(prev!=NULL && root->data <= prev->data) { return 0; } prev = root; return isBST(root->right); } else{ return 1; } }

11. Code int main() { // Constructing the root node - Using Function struct node *p = createNode(5); struct node *p1 = createNode(3); struct node *p2 = createNode(6); struct node *p3 = createNode(1); struct node *p4 = createNode(4); // Finally The tree looks like this: // 5 // / \ // 3 6 // / \ // 1 4

12. Code // Linking the root node with left and right children p->left = p1; p->right = p2; p1->left = p3; p1->right = p4; // preOrder(p); // printf("\n"); // postOrder(p); // printf("\n"); inOrder(p); printf("\n"); // printf("%d", isBST(p)); if(isBST(p)){ printf("This is a bst" ); } else{ printf("This is not a bst"); } return 0; }

13. Seacrhing in a binary search tree T his is one of the fastest searching mechanism it can be apply for long list it use a special algorithm Divide N conquer Searching in BST is very fats accessing comparing to array, linked list , etc. We can search key value in huge amount of data is very fast using

14. Search function Struct Node *search (Struct node* root , int key) { if (root==NULL) { return NULL; } if(key==root->data) { return root; } else if(key <root->data) { retrun search(root->left , key); } else { retrun search(root->right , key); } } 5 / \ 3 6 / \ 1 4

15. Minimum And Maximum value in BST Node * minElement (Node *root) { if (root==null) return null; else if(root->left!=null) return root; else minElement (root- >left) return } Node * maxElement (Node *root) { if (root==NULL) return NULL; else if( root->right = = NULL ) return root; else maxElement (root->left) return }

16. Insertion a node in Binary S earch Tree There are no duplicate value in a bst If insert at some internal position and not at the leaf Create that node and allocate memory to it in heap using malloc. Initialize the node with data given and ,both left and right marked NULL.

17. In BST duplicate value not allow If I want to insert 7 in below BST diagram not allow I want to insert 10 in below BST 10

18. Insertion in BST Void insert (node* root, int key) { node* prev=NULL; newNode* ptr; While(root!=null){ Prev =root If ( key == root->data ) return; Elif (key<root->data) Root=root->left Else Root=root->right } linked the nodes; }

19. void insert(struct node *root, int key){ struct node *prev = NULL; while(root!=NULL){ prev = root; if(key==root->data) { printf("Cannot insert %d, already in BST", key); return; } else if(key<root->data) { root = root->left; } else{ root = root->right; } } struct node* new = createNode(key); if(key<prev->data){ prev->left = new; } else{ prev->right = new; } }

20. Deletion a node in BST Case1. The node is leaf node Serach node and delete it Case2. The node is a non leaf node Case3. The node is root node Step1. search for the node Step2. search for InOrder predecessor(leftsubtree rightmost node) and InOrder post Keep doing this until the free has empty node

21. Deletion a node in bst Delete leaf Delete 7 node Delete root

22. bst struct Node* deleteNode(struct Node* root, int k ) { // Base case if (root == NULL) return root; // Recursive calls for ancestors of // node to be deleted if (root->key > k) { root- >left = deleteNode(root->left, k); return root; } else if (root->key < k ) { root- >right = deleteNode(root->right, k); return root; } // We reach here when root is the node // to be deleted. // If one of the children is empty if (root->left == NULL) { struct Node* temp = root->right; free(root); return temp; } else if (root->right == NULL ) { struct Node* temp = root->left; free(root); return temp; }

23. THANK YOU