Binary Search Tree in C/C++

Binary search tree (BST) is a kind of Binary tree that satisfies the following property for every node x:

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then info[y] <= info[x]. If y is a node in the right subtree of x, then info[y] >= info[x]. 

Binary search trees are data structures that support many dynamic-set operations like SEARCH, INSERT, DELETE, PREDECESSOR etc. Basic operations on a binary search tree take time proportional to the height of binary tree ie O(n) in worst case. For a balanced binary search tree of n nodes, these operations take O(logn) time.

Binary Search Tree

Implementing Binary Search Tree in C/C++

Inserting into a Binary Search Tree (BST)
Tree-Insert (root, z)
1. if root == NULL:
     return create(z)
3. else if z < info[root]
        left[root] = Tree-Insert (left[root], z)
   else
        right[root] = Tree-Insert (right[root], z)
4. return root
Searching in a Binary Search Tree (BST)
Tree-Search (root, k)
1. if root = NULL or k = info[root]
2.   return root
3. if k < info[root]:
4.   return Tree-Search (left[root], k)
5. else
6.   return Tree-Search (right[root], k)

Code Implementation

//
//  main.cpp
//  Binary Search Tree (Basic)
//
//  Created by Himanshu on 16/09/21.
//

#include <iostream>
using namespace std;

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

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

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

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

int main() {
    Node *root = newNode(5);
    insert(root, 3);
    insert(root, 2);
    insert(root, 4);
    insert(root, 7);
    
    //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 8 in the tree
    if (search (root, 8)) {
        cout<<"8 is present in the BST"<<endl;
    } else {
        cout<<"8 is not in the BST"<<endl;
    }
    
    return 0;
}

Here’s a working example:

https://ideone.com/qYS7ug

In the next post, we’ll learn about much complex operations on binary search trees.

Leave a Reply

Your email address will not be published.