Find min and max in a binary search tree

In this article we will see how to implement find minimum and find maximum in a binary search tree.

Find Min

The find_min should return the node with the smallest key. So, for example given the BST in the diagram.

          f
      
    c             m

a       e     g

     d            j

The find_min must return the node ‘a’. In the BST below:

          f
      
    c             m

        e     g

     d            j

the find_min should return the node ‘c’.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def find_min(root)
  if root.nil?
    return
  end
  
  if root.left.nil?
    return root
  else
    return find_min(root.left)
  end
end

Find Max

The find_max should return the node with the greatest key. So, for example given the BST in the diagram.

          f
      
    c             m

a       e     g

     d            j

The find_max must return the node ’m’.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def find_max(root)
  if root.nil?
    return
  end
  
  if root.right.nil?
    return root
  else
    return find_max(root.right)
  end
end