Binary Search Tree in C/C++[2]

In the last post we learnt about Binary Search Trees and basic operations like insert and search on them. In this post we’ll learn about some complex operations on them.

Binary Search Tree

Implementing Binary Search Tree operations in C/C++

Finding Minimum Element

Tree-Minimum (root)
1. while (left[root] != NULL)
2. root = left[root]
3. return root

Finding Maximum Element

Tree-Maximum (root)
1. while (right[root] != NULL)
2.   root = right[root]
3. return root

Note: Given a node in a binary search tree, it is sometimes required to find its successor and predecessor in the sorted order determined by an inorder traversal

Inserting into a Binary Search Tree (BST) and saving parent node (predecessor)
Tree-Insert (root, z, parent) // parent is to store parent node
1. if root == NULL
2.   return create(z, parent)
3. if info[root] < z
4.   parent = root
5.   right[root] = Tree-Insert(right[root], z)
6. if info[root] > z
7.   parent = root
8.   left[root] = Tree-Insert(left[root], z)
9  return root

Finding Successor

Tree-Successor (x)
1. if right[x] != NULL
2. return Tree-Minimum (right[x])
3. y = parent[x]
4. while y != NULL and x == right[y]
5. do x = y
6. y = parent[y]
7. return y

Deleting a node from Binary Search Tree (BST) (requires pointer to the parent Node)

Tree-Delete (T, x)
1. if left[x] != NULL && right[x] != NULL //If x (node to be deleted) have both children
2.   z = Tree-Successor (x)
3.   info[x] = info[z]
4.   x = z            
// Now z is the node to be deleted, since it has either 1 or o child
5. par = parent[x]
6. if left[x] != NULL 
7.   if left[par] == x // If x is the left child
8.     left[par] = left[x]
9.   else
10.    right[par] = left[x]
11. if right[x] != NULL 
12.   if left[par] == x 
13.     left[par] = right[x]
14.   else
15.    right[par] = right[x]
16. if right[x] == NULL  && right[x] == NULL 
17.   if left[par] == x 
18.     left[par] = NULL
19.   else
20.     right[par] = NULL
21. return root[T]

Code Implementation

//
//  main.cpp
//  Binary Search Tree [2]
//
//  Created by Himanshu on 16/09/21.
//

#include <iostream>
using namespace std;

struct node {
    int info = 0;
    struct node *left, *right, *parent;
};
typedef struct node Node;

node* newNode(int data, Node *par) {
    node* Node = new node();
    Node->info = data;
    Node->left = NULL;
    Node->right = NULL;
    Node->parent = par;
 
    return(Node);
}


Node* insert (Node *root, int n, Node *par) {

    if (root == NULL) {
        root = newNode(n, par);
    } else {
        if (root->info > n) {
            par = root;
            root->left = insert (root->left, n, par);
        } else {
            par = root;
            root->right = insert (root->right, n, par);
        }
    }

    return root;
}


Node* search (Node *root, int n) {

    if (root == NULL || root->info == n) {
        return root;
    } else {
        if (root->info > n) {
            return search (root->left, n);
        } else {
            return search (root->right, n);
        }

    }
}


Node* findMinimum (Node *root) {

    while (root->left != NULL) {
        root = root->left;
    }

    return root;
}


Node* findMaximum (Node *root) {

    while (root->right != NULL) {
        root = root->right;
    }

    return root;
}


Node* findSuccessor (Node *root) {

    if (root->right != NULL) {
        return findMinimum(root->right);
    }

    Node* y = root->parent;

    while (y != NULL && root == y->right) {
        root = y;
        y = y->parent;
    }

    return y;
}


Node* deleteNode (Node *root, Node *x) {
    Node *par = x->parent;
    
    if (x->left != NULL && x->right != NULL) {
        Node* z = findSuccessor(x);
        x->info = z->info;
        x = z;
    }
    
    par = x->parent;
    
    if (x->left != NULL) {

        if (par) {
            if (par->left == x) {
                par->left = x->left;
            } else {
                par->right = x->left;
            }
        } else {
            root = par->left;
        }

        // To prevent memory leak
        delete (x);
    } else if (x->right != NULL) {

        if (par) {
            if (par->left == x) {
                par->left = x->right;
            } else {
                par->right = x->right;
            }
        } else {
            root = par->right;
        }

        // To prevent memory leak
        delete (x);
    } else {

        if (par) {
            if (par->left == x) {
                par->left = NULL;
            } else {
                par->right = NULL;
            }
        } else {
            root = NULL;
        }

        // To prevent memory leak
        delete (x);
    }
    
    return root;
}


int main() {
    Node *root = newNode(5, NULL);
    root = insert(root, 3, NULL);
    root = insert(root, 2, NULL);
    root = insert(root, 4, NULL);
    root = insert(root, 7, NULL);
    
    //Searching 4 in the tree
    if (search (root, 4)) {
        cout<<"4 is present in the BST"<<endl;
    } else {
        cout<<"4 is not in the BST"<<endl;
    }

    //Searching parent of node 3 in the tree
    Node *node = search (root, 3);
    if (node->parent) {
        cout<<"Parent of node 3 is "<<(node->parent->info)<<endl;
    } else {
        cout<<"Parent of node is NULL"<<endl;
    }
    
    //Searching successor of node 2 in the tree
    node = search (root, 2);
    if (node) {
        cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
    } else {
        cout<<"Successor of node 2 is NULL"<<endl;
    }
    
    //Deleting node 3 in the tree
    cout<<"Deleting node 3"<<endl;
    root = deleteNode(root, search (root, 3));
    
    // Checking if node 3 exists in the tree
    if (search (root, 3)) {
        cout<<"3 is present in the BST"<<endl;
    } else {
        cout<<"3 is not in the BST"<<endl;
    }
    
    //Searching successor of node 2 in the tree
    node = search (root, 2);
    if (node) {
        cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
    } else {
        cout<<"Successor of node 2 is NULL"<<endl;
    }
    
    //Searching successor of node 4 in the tree
    node = search (root, 4);
    if (node) {
        cout<<"Successor of node 4 is "<<(findSuccessor(node)->info)<<endl;
    } else {
        cout<<"Successor of node 4 is NULL"<<endl;
    }
    
    return 0;
}

Output

4 is present in the BST
Parent of node 3 is 5
Successor of node 2 is 3
Deleting node 3
3 is not in the BST
Successor of node 2 is 4
Successor of node 4 is 5

Here’s a working example:
https://ideone.com/GU0vlP

8 thoughts on “Binary Search Tree in C/C++[2]

  1. Słowa mają ogromną moc, Ja bardzo w to wierze. Mogą inspirować, dawać motywację lub pocieszenie, a gdy go potrzeba. Czasem w jednym zdaniu jak zaklęta jest madrość, której szukamy w życiu przez bardzo długi czas. Twój blog to dosadnie urzeczywistnia!

  2. Wspaniały blog wiele przydatnych informacji zawartych w poszczególnych postach, Dzięki Ci za to serdeczne, zapraszam także do siebie…

  3. I was checking the internet for some info since yesterday night and I ultimately found what i was looking for! This is a excellent web site by the way, although it is a little bit off place from my smart phone.

Leave a Reply

Your email address will not be published.