Binary Search Tree removal using recursion

Question

When removing a node from a binary search tree, you either replace the node with its biggest child on the left or its smallest child on the right.

I'm having a hard time understanding the way the following implementation executes the the removal operation.

@discardableResult public func remove() -> BinarySearchTree? {
  let replacement: BinarySearchTree?

  // Replacement for current node can be either biggest one on the left or
  // smallest one on the right, whichever is not nil
  if let right = right {
    replacement = right.minimum()
  } else if let left = left {
    replacement = left.maximum()
  } else {
    replacement = nil
  }

  // Recursion
  replacement?.remove()

  // Place the replacement on current node's position
  replacement?.right = right
  replacement?.left = left
  right?.parent = replacement
  left?.parent = replacement
  reconnectParentTo(node:replacement)

  // The current node is no longer part of the tree, so clean it up.
  parent = nil
  left = nil
  right = nil

  return replacement
}

The above code consists of following steps:

1. Find a replacement node.
2. Have the replacement node refer the removed node's right and left child.
3. Have the right and the left child of the removed node refer to the replacement node as a parent.
4. Have the replacement node refer to the removed node's parent as its own parent.
5. Clean up.

The part I'm having difficulty specifically is the recursion. As far as I understand, the base case of the recursion is replacement = nil because as long as there is either a right child or a left child, the recursion will continue to occur. However, how can replacement be nil when it's supposed to refer for the replacement node? At the same time, how does the recursion stop if replacement isn't nil?

Answer 1

It may help to see what happens visually. Let's say you start with this tree and want to remove the orange root node

You call remove on the orange node:

• self is orange.
• replacement is the minimum of the right subtree - the blue node.

You recurse by calling remove on blue:

• self is blue
• replacement is nil as blue has neither left nor right children
• You call remove on nil (or rather you don't, because of the ?)
• Similarly, all of the other assignments are skipped because the optional values are all nil
• reconnectParent(node: nil) is called to fix the left/right linkage of blue's parent (this will result in green.left being assigned nil)
• You return blue

The tree now looks like:

You are now back out at the initial call to remove and execution continues. Remember,

• self is orange.
• replacement is blue node.

The next steps are:

• blue.right = orange.right
• blue.left = orange.left
• orange.right.parent = blue
• orange.left.parent = blue
• orange.reconnectParentTo(node:blue) - This does nothing since orange has no parent
• orange.parent = nil
• orange.right = nil
• orange.left = nil
• Return from remove - This was the initial call to remove, so we have exited all recursion

This leaves us with the final tree: