Scribd
Upload
7 views5 pages

BST Assignment With Examples

The document outlines the implementation of a Binary Search Tree (BST) in C, detailing algorithms for inserting and deleting nodes, as well as tree traversal techniques. It provides code examples for creating nodes, inserting elements, deleting nodes based on three cases, and performing inorder, preorder, and postorder traversals. The document also includes a visual representation of the tree structure during various operations.

Uploaded by

debdattakar24
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views5 pages

BST Assignment With Examples

The document outlines the implementation of a Binary Search Tree (BST) in C, detailing algorithms for inserting and deleting nodes, as well as tree traversal techniques. It provides code examples for creating nodes, inserting elements, deleting nodes based on three cases, and performing inorder, preorder, and postorder traversals. The document also includes a visual representation of the tree structure during various operations.

Uploaded by

debdattakar24
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Binary Search Tree (BST) Assignment

1. Algorithm to Insert an Element in BST

In a Binary Search Tree (BST):

- All elements in the left subtree are less than the node.

- All elements in the right subtree are greater than the node.

Example:

Insert 50, 30, 70, 20, 40, 60, 80

The tree becomes:

50

/ \

30 70

/\ /\

20 40 60 80

C Code:

struct Node {

int data;

struct Node* left;

struct Node* right;

};

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

struct Node* insert(struct Node* root, int data) {


Binary Search Tree (BST) Assignment

if (root == NULL)

return createNode(data);

if (data < root->data)

root->left = insert(root->left, data);

else if (data > root->data)

root->right = insert(root->right, data);

return root;

2. Deletion in BST (Three Cases)

Three cases when deleting from a BST:

1. Leaf Node: Delete 20

2. One Child: Delete 30 (assume only left child)

3. Two Children: Delete 50

Tree before deleting 50:

50

/ \

30 70

/\ /\

20 40 60 80

Inorder successor of 50 is 60

After deleting 50:

60

/ \

30 70

/\ \

20 40 80
Binary Search Tree (BST) Assignment

C Code:

struct Node* findMin(struct Node* node) {

while (node->left != NULL)

node = node->left;

return node;

struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL) return root;

if (key < root->data)

root->left = deleteNode(root->left, key);

else if (key > root->data)

root->right = deleteNode(root->right, key);

else {

if (root->left == NULL && root->right == NULL) {

free(root);

return NULL;

} 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 = findMin(root->right);

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

return root;
Binary Search Tree (BST) Assignment

3. Tree Traversal Techniques

Three traversal types:

1. Inorder (Left, Root, Right)

2. Preorder (Root, Left, Right)

3. Postorder (Left, Right, Root)

Example Tree:

50

/ \

30 70

/\ /\

20 40 60 80

Inorder: 20 30 40 50 60 70 80

Preorder: 50 30 20 40 70 60 80

Postorder: 20 40 30 60 80 70 50

C Code:

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

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

inorder(root->right);

void preorder(struct Node* root) {

if (root != NULL) {
Binary Search Tree (BST) Assignment

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);

You might also like