Table Of Content
Search a node in BST #
Given a Binary Search Tree and a node value X, find if the node with value X is present in the BST or not.
The idea is to use the fact that the given tree is a BST. So, instead of transverting every node, we can use the binary search algorithm.
- Time Complexity : O(h)
- Space Complexity : O(1)
bool search(Node* root, int x) {
if (!root) return false;
while(root){
if(root->data == x)
return true;
if(root->data < x)
root = root->right;
else
root = root->left;
}
return false;
}
Search a node in BST #
Given a Binary Search Tree and a node value X, find if the node with value X is present in the BST or not.
The idea is to use the fact that the given tree is a BST. So, instead of transverting every node, we can use the binary search algorithm.
- Time Complexity : O(h)
- Space Complexity : O(1)
bool search(Node* root, int x) {
if (!root) return false;
while(root){
if(root->data == x)
return true;
if(root->data < x)
root = root->right;
else
root = root->left;
}
return false;
}