In last post insert a node in BST, we learned basics about binary search tree and how to insert a node in it. Today, we will discuss how to search a value in binary search tree.
As we already know that binary search tree has this property where all nodes on left side of node are smaller and all nodes on right side of node are greater than it. So, when searching for a value in BST, we can safely discard half of tree (given tree balanced) with each comparison. Remember something? Binary search algorithm!!
Algorithm to search in binary search tree
1. Start with root node, make it currentNode 2. While currentNode is not NULL 2.1 Compare currentNode->value with searchedKey 2.1.1 If currentNode->value == searchedKey, return currentNode 2.1.2 If currentNode->value > searchedKey, make currentNode = currentNode->left; 2.1.3 If currentNode->value < searchedKey make currentNode = currentNode->right; 3. return currentNode;
Implementation is pretty simple and classic case for divide and conquer algorithm.
Recursive implementation of same is :
Complexity of search in binary search tree in worst case is O(N). Again misconception that it is O(log N). It is O(log N) only when it is given that BST is balanced. If tree is completely skewed, complexity is O(N)
Please share if you find something wrong or missing. Sharing is caring.