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

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