Search in Binary Search Tree
excerpt: This covers implementation of search functionality in Binary Search Tree. tags: tailrecursion twowaycomparison
The search method searches for some item with a known key in a binary search tree and retrieves the associated item. The method takes a parameter called key to search in the tree.
Searching in BST
The size of the problem is the height of the tree. A trivial base case occurs when the binary tree is empty. In this case, we can return. There is another case where recursive calls are not made. If the key of the root node is k, the item is found and therefore it can be returned. Thus, in the recursive cases we can be sure that the root node does not contain the searched item.
The next step is to find an appropriate decomposition of the problem that reduces its size. Trees are composed recursively of subtrees. Consider searching for the item in the two subtrees of the binary search tree. Thus, the size of problem is reduced by one unit, since the root node is discarded.
In this problem we can also avoid searching the entire subtree. If the key is less than the root value, then the item will not be in the right subtee, due to the binary search tree property. The search method searches a node’s subtree for a target value.


The base case checks if the node is nil, if so it returns from the recursive call. Then the node value is checked to see if it is equal to the target value, if so it returns the current node.
If the target value is less than the current node’s value, the search recursive call searches for the target in the left subtree. If the target value is greater than the current node’s value, search call is made on the right subtree.
The height of the binary tree determines the cost of the algorithm in the worst case. A balanced tree has approximately the same number of nodes on the left and right subtrees of nodes that appear on the same level. In a balanced tree, if the tree contains N nodes, the height of the tree is O(log N), so the run time of search is O(log N). Each recursive call discards approximately half of the nodes. However the tree could have a linear structure, in which case the algorithm will run in O(n).