Binary Search Tree (BST) Deletion

Deletion in a Binary Search Tree (BST) is more complex than insertion or search because the tree’s ordering property must be preserved after removing a node. The strategy used depends on how many children the node to be deleted has.

Understanding deletion is essential before moving on to self-balancing trees.

Deletion Cases

When deleting a node from a BST, one of three cases applies:

Case 1 - Leaf Node (No Children)

If the node has no children, it can be removed directly.

Before:        After:
    5              5
   / \            /
  3   7          3

Case 2 - One Child

If the node has one child, replace the node with its child.

Before:        After:
    5              5
     \              \
      7              8
       \
        8

Case 3 - Two Children

If the node has two children:

1. Find the in-order successor (smallest value in the right subtree)
2. Replace the node’s value with the successor’s value
3. Delete the successor node from the right subtree

Before:               After:
        8                   9
       / \                 / \
      3   10      →       3   10
           \                   \
            9                   (removed)

This preserves the BST ordering property.

Rust Implementation

Below is a recursive BST deletion implementation that handles all three cases.

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub left: Option<Box<Node<T>>>,
    pub right: Option<Box<Node<T>>>,
}

impl<T: Ord> Node<T> {
    pub fn new(value: T) -> Self {
        Node {
            value,
            left: None,
            right: None,
        }
    }

    pub fn delete(self: Box<Self>, value: &T) -> Option<Box<Node<T>>> {
        if value < &self.value {
            let left = self.left.and_then(|node| node.delete(value));
            Some(Box::new(Node {
                value: self.value,
                left,
                right: self.right,
            }))
        } else if value > &self.value {
            let right = self.right.and_then(|node| node.delete(value));
            Some(Box::new(Node {
                value: self.value,
                left: self.left,
                right,
            }))
        } else {
            match (self.left, self.right) {
                (None, None) => None,
                (Some(child), None) | (None, Some(child)) => Some(child),
                (Some(left), Some(right)) => {
                    let (successor_value, new_right) = extract_min(right);
                    Some(Box::new(Node {
                        value: successor_value,
                        left: Some(left),
                        right: new_right,
                    }))
                }
            }
        }
    }
}

fn extract_min<T: Ord>(mut node: Box<Node<T>>) -> (T, Option<Box<Node<T>>>) {
    match node.left {
        Some(left) => {
            let (min, new_left) = extract_min(left);
            node.left = new_left;
            (min, Some(node))
        }
        None => (node.value, node.right),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_deletes_nodes() {
        let mut root = Box::new(Node::new(8));
        root.left = Some(Box::new(Node::new(3)));
        root.right = Some(Box::new(Node::new(10)));
        root.right.as_mut().unwrap().right = Some(Box::new(Node::new(14)));

        let root = root.delete(&10).unwrap();
        assert_eq!(root.right.as_ref().unwrap().value, 14);
    }
}

Example Usage

fn main() {
    let mut root = Box::new(Node::new(8));
    root.left = Some(Box::new(Node::new(3)));
    root.right = Some(Box::new(Node::new(10)));
    root.left.as_mut().unwrap().left = Some(Box::new(Node::new(1)));
    root.left.as_mut().unwrap().right = Some(Box::new(Node::new(6)));

    let root = root.delete(&3);

    println!("{:#?}", root);
}

Time and Space Complexity

BST deletion has the same complexity characteristics as search and insertion.

Time Complexity

Worst case occurs when the tree is skewed.

Space Complexity

Key Takeaways

• Deletion must preserve the BST ordering property
• The in-order successor is commonly used for nodes with two children
• Unbalanced BSTs can degrade performance

Playground Links

Rust - BST Deletion