Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    BST Program

    Uploaded by

    oyezoroo
    Binary search tree in dsa

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    BST Program

    Uploaded by

    oyezoroo
    2 views4 pages
    Binary search tree in dsa

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Binary search tree in dsa

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    2 views4 pages

    BST Program

    Uploaded by

    oyezoroo
    Binary search tree in dsa

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 4

    #include <stdio.

    h>
    #include <stdlib.h>
    struct node {
    int key;
    struct node *left, *right;
    };
    // Create a node
    struct node *newNode(int item) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
    }
    // Inorder Traversal
    void inorder(struct node *root) {
    if (root != NULL) {
    inorder(root->left);
    printf("%d -> ", root->key);
    inorder(root->right);
    }
    }
    // Insert a node
    struct node *insert(struct node *node, int key) {
    // Return a new node if the tree is empty
    if (node == NULL)
    return newNode(key);
    // Traverse to the right place and insert the node
    if (key < node->key)
    node->left = insert(node->left, key);
    else
    node->right = insert(node->right, key);
    return node;
    }
    // Find the inorder successor
    struct node *minValueNode(struct node *node) {
    struct node *current = node;
    // Find the leftmost leaf
    while (current && current->left != NULL)
    current = current->left;
    return current;
    }
    // Deleting a node
    struct node *deleteNode(struct node *root, int key) {
    // Return if the tree is empty
    if (root == NULL) return root;
    // Find the node to be deleted
    if (key < root->key)
    root->left = deleteNode(root->left, key);
    else if (key > root->key)
    root->right = deleteNode(root->right, key);
    else {
    // If the node is with only one child or no child
    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, 8);
    root = insert(root, 3);
    root = insert(root, 1);
    root = insert(root, 6);
    root = insert(root, 7);
    root = insert(root, 10);
    root = insert(root, 14);
    root = insert(root, 4);
    printf("Inorder traversal: ");
    inorder(root);
    printf("\nAfter deleting 10\n");
    root = deleteNode(root, 10);
    printf("Inorder traversal: ");
    inorder(root);
    }
    Result:
    Inorder traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 14 ->
    After deleting 10
    Inorder traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 14 ->

    You might also like