Skip to content

Instantly share code, notes, and snippets.

@shahzaib-sheikh

shahzaib-sheikh/tree.c

Created February 18, 2024 03:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save shahzaib-sheikh/15b83dac831e2dbb1af4fa4c8d5caa16 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save shahzaib-sheikh/15b83dac831e2dbb1af4fa4c8d5caa16 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. shahzaib-sheikh created this gist Feb 18, 2024.
    336 changes: 336 additions & 0 deletions tree.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,336 @@
    #include <stdio.h>
    #include <stdlib.h>

    typedef struct Node
    {
    int data;
    struct Node *right;
    struct Node *left;
    int count;
    } Node;

    typedef struct Tree
    {
    int nodesCount;
    Node *root;
    } Tree;

    Node *initializeNode();
    Tree *initializeTree();
    void printTree(Tree *tptr);
    void printTreeFromNode(Node *nptr, int order);
    void insertIntoTree(Tree *tptr, int data);
    int insertIntoTreeRecursive(Tree *tptr, int data);
    int insertIntoTreeByNodeRecursive(Node *nptr, int data, Node **toBeUpdated);
    Node *searchInTree(Tree *tptr, int data);
    int mod(int number);
    Node *getMinimumNodeAddress(Node **nptr, int detach);

    int main()
    {
    Tree *tptr = initializeTree();
    getchar();
    // insertIntoTree(tptr, 56);
    // insertIntoTree(tptr, 76);
    // insertIntoTree(tptr, 89);
    // insertIntoTree(tptr, 45);
    // insertIntoTree(tptr, 12);
    // insertIntoTree(tptr, 213);
    // insertIntoTree(tptr, 134);
    // insertIntoTree(tptr, -65);
    // insertIntoTree(tptr, 423);
    // insertIntoTree(tptr, 32);
    // insertIntoTree(tptr, 7);
    insertIntoTreeRecursive(tptr, 56);
    insertIntoTreeRecursive(tptr, 76);
    insertIntoTreeRecursive(tptr, 89);
    insertIntoTreeRecursive(tptr, 45);
    insertIntoTreeRecursive(tptr, 12);
    insertIntoTreeRecursive(tptr, 213);
    insertIntoTreeRecursive(tptr, 134);
    insertIntoTreeRecursive(tptr, -65);
    insertIntoTreeRecursive(tptr, 423);
    insertIntoTreeRecursive(tptr, 32);
    insertIntoTreeRecursive(tptr, 7);
    printTree(tptr);
    // deleteFromTree(tptr,32);
    deleteFromTree(tptr, 56);
    // deleteFromTree(tptr,89);
    // deleteFromTree(tptr,7);
    deleteFromTree(tptr, -65);
    // deleteFromTree(tptr,12);
    deleteFromTree(tptr, 76);
    // deleteFromTree(tptr,45);
    // deleteFromTree(tptr,134);
    deleteFromTree(tptr, 213);
    // deleteFromTree(tptr,423);
    // printTree(tptr);
    printTree(tptr);
    searchInTree(tptr, 56);
    searchInTree(tptr, 45);
    searchInTree(tptr, 134);
    }

    void printTree(Tree *tptr)
    {
    puts("\tPrinting Tree");
    printTreeFromNode(tptr->root, 1);
    }

    int mod(int number)
    {
    if (number < 0)
    {
    return number * -1;
    }
    return number;
    }

    int insertIntoTreeRecursive(Tree *tptr, int data)
    {
    tptr->nodesCount++;
    return insertIntoTreeByNodeRecursive(tptr->root, data, &tptr->root);
    }

    int deleteFromTree(Tree *tptr, int data)
    {
    if (tptr->root == NULL)
    {
    puts("\nEmpty Tree");
    return 0;
    }
    Node *temp = tptr->root;
    Node **toBeUpdatedPrevious = &tptr->root;

    while (temp != NULL)
    {
    if (temp->data == data)
    {
    if (temp->count > 1)
    {
    temp->count--;
    return 1;
    }
    break;
    }
    if (temp->data > data)
    {
    toBeUpdatedPrevious = &temp->left;
    temp = temp->left;
    }
    else
    {
    toBeUpdatedPrevious = &temp->right;
    temp = temp->right;
    }
    }
    if (temp == NULL)
    {
    puts("\nvalue not found");
    return 0;
    }

    if (temp->right == NULL)
    {
    *toBeUpdatedPrevious = temp->left;
    free(temp);
    return 1;
    }
    Node *minimum = getMinimumNodeAddress(&temp->right, 1);
    minimum->left = temp->left;
    minimum->right = temp->right;
    *toBeUpdatedPrevious = minimum;
    free(temp);
    return 1;
    }

    Node *getMinimumNodeAddress(Node **nptr, int detach)
    {
    Node *current = *nptr;
    Node **tobeUpdated = nptr;
    int check = 0;
    while (1)
    {
    if (current->left != NULL)
    {
    tobeUpdated = &current->left;
    current = current->left;
    check = 1;
    }
    else
    {
    if (detach && check)
    {
    *tobeUpdated = NULL;
    }
    else
    {
    *tobeUpdated = current->right;
    }
    return current;
    }
    }
    }

    int insertIntoTreeByNodeRecursive(Node *nptr, int data, Node **toBeUpdated)
    {
    if (nptr == NULL)
    {
    Node *temp = initializeNode();
    temp->data = data;
    *toBeUpdated = temp;
    return 1;
    }
    else
    {
    if (nptr->data == data)
    {
    nptr->count++;
    return 1;
    }
    if (nptr->data > data)
    {
    insertIntoTreeByNodeRecursive(nptr->left, data, &nptr->left);
    }
    else
    {
    insertIntoTreeByNodeRecursive(nptr->right, data, &nptr->right);
    }
    return 1;
    }
    }

    Node *searchInTree(Tree *tptr, int data)
    {
    if (tptr->root == NULL)
    {
    puts("\nEmpty Tree");
    return NULL;
    }
    Node *temp = tptr->root;
    while (temp != NULL)
    {
    if (temp->data == data)
    {
    puts("\nvalue found");
    if (temp == tptr->root)
    {
    puts("root node");
    }
    else if (temp->left == NULL && temp->right == NULL)
    {
    puts("leaf node");
    }
    else
    {
    puts("internal node");
    }
    printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", temp->data, temp, temp->left, temp->right, temp->count);
    return temp;
    }
    if (temp->data > data)
    {
    temp = temp->left;
    }
    else
    {
    temp = temp->right;
    }
    }
    puts("\nvalue not found");
    return NULL;
    }

    void printTreeFromNode(Node *nptr, int order)
    {
    if (nptr == NULL)
    {
    return;
    }
    // preorder
    if (order == 1)
    {
    printTreeFromNode(nptr->left, order);
    printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", nptr->data, nptr, nptr->left, nptr->right, nptr->count);
    printTreeFromNode(nptr->right, order);
    return;
    }
    // inorder
    if (order == 2)
    {
    printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", nptr->data, nptr, nptr->left, nptr->right, nptr->count);
    printTreeFromNode(nptr->left, order);
    printTreeFromNode(nptr->right, order);
    return;
    }
    // postorder
    if (order == 3)
    {
    printTreeFromNode(nptr->left, order);
    printTreeFromNode(nptr->right, order);
    printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", nptr->data, nptr, nptr->left, nptr->right, nptr->count);
    return;
    }
    }

    Tree *initializeTree()
    {
    Tree *ptr = (Tree *)malloc(sizeof(Tree));
    ptr->nodesCount = 0;
    ptr->root = NULL;
    return ptr;
    }

    void insertIntoTree(Tree *tptr, int data)
    {
    if (tptr->root == NULL)
    {
    tptr->root = initializeNode();
    tptr->root->data = data;
    tptr->root->count++;
    }
    else
    {
    Node *temp = tptr->root;
    Node *previous = NULL;
    while (temp != NULL)
    {
    if (temp->data == data)
    {
    temp->count++;
    return;
    }
    previous = temp;
    if (temp->data > data)
    {
    temp = temp->left;
    }
    else
    {
    temp = temp->right;
    }
    }
    Node *newNode = initializeNode();
    newNode->data = data;
    newNode->count++;
    if (previous->data > data)
    {
    previous->left = newNode;
    }
    else
    {
    previous->right = newNode;
    }
    tptr->nodesCount++;
    }
    }

    Node *initializeNode()
    {
    Node *ptr = (Node *)malloc(sizeof(Node));
    ptr->data = 0;
    ptr->right = NULL;
    ptr->left = NULL;
    ptr->count = 0;
    return ptr;
    }