Node* BinarySearchTree::search(Node *root, int key) {
    if (!root || root->val == key) {
        return root;
    }

    if (root->val < key) {
        return search(root->right, key);
    }
    return search(root->left, key);
}