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.
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;
}
Output
4 is present in the BST 8 is not in the BST
Here’s a working example: Binary Search Tree
In the next post, we’ll learn about more complex operations on binary search trees.