What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree.

Question

Suresh Chand · Accepted Answer

Binary Search Tree is a binary tree that is either empty or in which every node contains a key and satisfy the following conditions: All keys in the left sub-tree of the root are smaller than the key in the root node. All the keys in the right sub tree are greater than the key in the root node. The left and right sub-trees of the root are again binary search trees. Example: BST tree of numbers: 50, 70, 60, 20, 90, 10, 40, 100 Program: #include #include struct node{ int key; struct node *left, *right; }; struct node *newNode(int item){ struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } void inorder(struct node *root){ if (root != NULL){ inorder(root->left); printf('%d -> ', root->key); inorder(root->right); } } struct node *insert(struct node *node, int key){ if (node == NULL) return newNode(key); if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; } struct node *minValueNode(struct node *node){ struct node *current = node; while (current && current->left != NULL) current = current->left; return current; } struct node *deleteNode(struct node *root, int key){ if (root == NULL) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else{ 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; } struct node *temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } int main(){ struct node *root = NULL; root = insert(root, 6); root = insert(root, 7); root = insert(root, 3); root = insert(root, 2); root = insert(root, 4); root = insert(root, 19); root = insert(root, 17); root = insert(root, 8); printf('Inorder traversal:'); inorder(root); printf('nAfter deleting 10n'); root = deleteNode(root, 10); printf('Inorder traversal: '); inorder(root); } The output of above program is Inorder traversal:2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 17 -> 19 -> After deleting 10 Inorder traversal: 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 17 -> 19 ->

What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree.

Leave your Answer:

Hits Counter

Question

What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree.

Leave your Answer: