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



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.