Search in Binary Search Tree

excerpt: This covers implementation of search functionality in Binary Search Tree. tags: tail-recursion two-way-comparison

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def search(key, node)
  # If the node does not have a left or right child
  # return from the recursive call
  if node.nil?
    return
  end
  
  # If we found the target value, return the root node
  if key == node.value
    return node
  end
  
  # Check if the target value is in the left or right subtree
  if key < node.value
    # Search the left subtree
    search(key, node.left)
  else
    # Search the right subtree
    search(key, node.right)
  end
end

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).