Search for an Element in BST

Textbook

Description:

Example:

Note

Idea:

Code:

Search for a value

TreeNode * searchRecursive(TreeNode *root, int key){
    if(root==NULL || root->val==key) return root;

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

TreeNode * searchIterative(TreeNode *root, int key){
    TreeNode *node=root;

    while(node!=NULL){
        if(node->val==key) return node; // Find key!

        if(node->val > key) node=node->left; // search left subtree
        else node=node->right; // search right subtree
    }

    return NULL; // Did not find the key
}

Search for Minimum or Maximum

// Minimum
TreeNode* searchMinimum(TreeNode *root){
    if(root==NULL) return NULL;
    TreeNode *node=root;
    while(node->left!=NULL){
        node=node->left;
    }
    return node;
}

// Maximum
TreeNode* searchMinimum(TreeNode *root){
    if(root==NULL) return NULL;
    TreeNode *node=root;
    while(node->right!=NULL){
        node=node->right;
    }
    return node;
}