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