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

By onlycode_oz40jdTrees

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, parent)
6. if info[root] > z
7.   parent = root
8.   left[root] = Tree-Insert(left[root], z, parent)
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 0 child
5. par = parent[x]
6. if left[x] != NULL  //Checking if x has a left child
7.   if left[par] == x // If x is the left child
8.     left[par] = left[x]
9.   else              // If x is the right child
10.    right[par] = left[x]
11. else if right[x] != NULL //Checking if x has a right child
12.   if left[par] == x 
13.     left[par] = right[x]
14.   else
15.     right[par] = right[x]
16. else if right[x] == NULL  && left[x] == NULL 
17.   if left[par] == x 
18.     left[par] = NULL
19.   else
20.     right[par] = NULL
21. Delete(x)
22. 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* createNode (int data, Node *par) {
    Node* newNode = new node();
    newNode->info = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = par;
 
    return (newNode);
}


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

    if (root == NULL) {
        root = createNode(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 = createNode(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 3 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: Binary Search Tree

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

  4. 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!

    Reply

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

    Reply

  6. 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.

    Reply

  8. Prawdziwy przyjaciel to nie ten, kto osusza łzy twoje, Niczm jak Drapieżne lwy Tołstoje, ale ten, kto nie pozwala ci ich wylewać, innym zabrania się z Ciebie wyśmiewać E. F. Teixeira & Zeroo Cool..

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *