Remove in Binary Search Tree

tags: create-link-with-return-value-from-recursion

In this article we will discuss how to implement remove operation in a binary search tree.

Remove Node

Consider the following binary search tree:

          k
      
    c             t

a       h     m

     f            p

One way to remove c can result in the BST:

          k
      
    a             t

        h     m

     f            p

The implementation discussed here results in the BST:

          k
      
    f             t

a       h     m

                  p

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

def remove(root, key)
  if root.nil?
    return
  end
  
  if key < root.key
    root.left = remove(root.left, key)
  elsif key > root.key
    root.right = remove(root.right, key)
  elsif root.left.nil?
    root = root.right
  elsif root.right.nil?
    root = root.left
  else
    root.key = find_min(root.right).key
    root.right = remove(root.right, root.key)
  end
  
  return root
end

Consider the case of removing the root node in the following binary search tree:

          k
      
    c             t

a       h     m

     f            p

The inorder successor of the root must take the place of the root.

Consider the following binary search tree:

          m
      
    c             t

a       h     _

     f            p

The child of inorder successor moves up to the vacant spot left by the inorder successor.

          m
      
    c             t

a       h     p

     f