## Binary Search Tree implementation in CPP and python

Binary Search Tree (BST) is a special binary tree where the key in each node must be greater than or equal to any key stored in the left subtree, and less than or equal to any key stored in the right subtree.
For example:

BSTs allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by last name).

Search, insert, and delete are the main operations of BST.

As the keys are stored in a particular order, the principle of binary search can be used for lookup.
We start from the root and compare the key. if the root has the key, it is returned as the result.
If the key is greater than the root, the right subtree is recursively checked.
If the key is less than the root, the left subtree is recursively checked.
The recursion continues until the key is found.

Insertion and deletion operations are much similar, as both use the same search logic to locate the needed node.

```#include <iostream>
#include <string>
using namespace std;

class Node {
public:
int data;
Node *left;
Node *right;
Node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};

Node* search(Node* root, int data) {
if (root == NULL) {
return NULL;
}
if (root->data == data) {
cout << "Found at: " << root << endl;
return root;
}
if (root->data < data)
return search(root->right, data);
else
return search(root->left, data);
}

void insert(Node* root, int data) {
if (root == NULL) {
Node *root = new Node(data);
}
else if (data <= root->data) {
if (root -> left != NULL)
insert(root->left, data);
else
root -> left = new Node(data);
}
else if (data > root->data) {
if (root -> right != NULL)
insert(root->right, data);
else
root -> right = new Node(data);
}
}

int main() {

Node *root = new Node(5);
insert(root, 3);
insert(root, 8);
insert(root, 1);
insert(root, 4);
insert(root, 7);
insert(root, 9);
insert(root, 0);
insert(root, 2);
insert(root, 6);
insert(root, 10);

search(root, 10);

delete [] root;

return 0;
}```

In python

```class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data

def search(root,data):
if root is None:
if root.data == data:
print("Found at:", hex(id(root)))
return root
if root.data < data:
return search(root.right,data)
else:
return search(root.left, data)

def insert(root,node):
if root is None:
root = node
else:
if root.data < node.data:
if root.right is None:
root.right = node
else:
insert(root.right, node)
else:
if root.left is None:
root.left = node
else:
insert(root.left, node)

root = Node(50)
insert(root,Node(30))
insert(root,Node(20))
insert(root,Node(40))
insert(root,Node(70))
insert(root,Node(60))
insert(root,Node(80))

search(root,70)```