Binary Search Tree

Node *insert(Node *root, int key){
    if (root==NULL) return new Node(key);
    // do not allow duplicates
    if (key < root->val)
        root->left = insert(root->left,key);
    else if (key > root->val)
        root->right = insert(root->right, key);
    return root;
};

bool search(Node *root, int key){
    if (root==NULL) return false;
    if (key<root->val) return search(root->left,key);
    else if (key>root->val) return search(root->right,key);
    return true;
}