Previous Lecture

Lecture 16

Next Lecture

Lecture 16, Tue 09/12

Binary Search Trees cont.

Recorded Lecture: 9_12_23

Case 3: Delete a node with two children

• First find the successor (node with next greater value) in the right subtree
  • This can be done by traversing the left children of the node to be deleted’s right subtree
  • Also note that the successor will always only have at most one child
    • If the successor had a left child, then it wouldn’t be the successor!
• Temporarily store the successor and delete the successor from the tree
  • Deleting the successor will fall in either Case 1 or Case 2
• Replace the deleted node’s value with the successor’s value