Binary Search Trees: Fast Lookups and Dynamic Data • Chillymosh's Blog

Binary Search Trees (BSTs) are one of the most important and widely used types of binary trees. By maintaining a sorted structure, BSTs provide efficient searching, insertion, and deletion operations at the heart of sets, maps, databases, and more.

In this post, we’ll cover:

What makes a tree a BST
Search, insertion, and deletion algorithms
Average vs worst-case performance
Common pitfalls and balancing needs
Practical code examples

What is a Binary Search Tree?#

A Binary Search Tree (also called an ordered or sorted binary tree) is a tree-based data structure where each node follows a strict organising rule: its value is greater than everything in its left subtree and less than everything in its right subtree. This ordering keeps the tree’s data sorted as you insert or remove nodes, which enables fast searching, insertion, and deletion. This is often much more efficient than a simple list.

Imagine a perfectly organised filing system where every bit of data knows exactly where it belongs. The performance of searching, inserting, or deleting all hinges on the tree’s height. Shorter, well-balanced trees deliver the best performance.

Left side: All values smaller than the current node
Right side: All values larger than the current node
Universal rule: This pattern holds true at every single node in the tree

This simple principle makes sure your data stays sorted, which makes searching incredibly fast.

Search#

How to efficiently find a value in a BST:

Start at the root.
If the value equals the root, you’re done.
If less, search the left subtree; if greater, search the right.
Repeat until found or you hit a leaf. If the latter then you would return None.

The time complexity for searching a BST for a value is O(h) where h is the height of the tree. If the tree is unbalanced then the height of the tree often becomes larger than it needs to be, which will cause searches to take longer.

Recursive#

def search(node, target):
    if node is None:
        return None
    if node.value == target:
        return node
    if target < node.value:
        return search(node.left, target)
    else:
        return search(node.right, target)

python

function search(node, target) {
  if (node === null) { 
    return null;
  }
  if (node.value === target) {
    return node
  };
  if (target < node.value) {
    return search(node.left, target)
  };
  return search(node.right, target);
}

func search(node *Node, target int) *Node {
    if node == nil {
        return nil
    }
    if node.Value == target {
        return node
    }
    if target < node.Value {
        return search(node.Left, target)
    }
    return search(node.Right, target)
}

Node search(Node node, int target) {
    if (node == null) {
        return null;
    }
    if (node.value == target) {
        return node;
    }
    if (target < node.value) {
        return search(node.left, target);
    }
    return search(node.right, target);
}

java

Node Search(Node node, int target) {
    if (node == null) {
        return null;
    }
    if (node.value == target) {
        return node;
    }
    if (target < node.value) {
        return Search(node.left, target);
    }
    return Search(node.right, target);
}

java

Node* search(Node* node, int target) {
    if (!node) {
        return nullptr;
    }
    if (node->value == target) {
        return node;
    }
    if (target < node->value) {
        return search(node->left, target);
    }
    return search(node->right, target);
}

cpp

struct Node* search(struct Node* node, int target) {
    if (node == NULL) {
        return NULL;
    }
    if (node->value == target) {
        return node;
    }
    if (target < node->value) {
        return search(node->left, target);
    }
    return search(node->right, target);
}

fn search(node: &Option<Box<Node>>, target: i32) -> Option<&Box<Node>> {
    match node {
        Some(n) => {
            if n.value == target {
                Some(n)
            } else if target < n.value {
                search(&n.left, target)
            } else {
                search(&n.right, target)
            }
        }
        None => None,
    }
}

Iterative#

def search(node, target):
    while node:
        if node.value == target:
            return node
        elif target < node.value:
            node = node.left
        else:
            node = node.right
    return None

python

function search(node, target) {
  while (node !== null) {
    if (node.value === target) {
        return node;
    }
    node = target < node.value ? node.left : node.right;
  }
  return null;
}

func search(node *Node, target int) *Node {
    for node != nil {
        if node.Value == target {
            return node
        }
        if target < node.Value {
            node = node.Left
        } else {
            node = node.Right
        }
    }
    return nil
}

Node search(Node node, int target) {
    while (node != null) {
        if (node.value == target) {
            return node;
        }
        node = (target < node.value) ? node.left : node.right;
    }
    return null;
}

java

Node Search(Node node, int target) {
    while (node != null) {
        if (node.value == target) {
            return node;
        }
        node = (target < node.value) ? node.left : node.right;
    }
    return null;
}

java

Node* search(Node* node, int target) {
    while (node) {
        if (node->value == target) {
            return node;
        }
        node = (target < node->value) ? node->left : node->right;
    }
    return nullptr;
}

cpp

struct Node* search(struct Node* node, int target) {
    while (node != NULL) {
        if (node->value == target) {
            return node;
        }
        node = (target < node->value) ? node->left : node->right;
    }
    return NULL;
}

fn search(mut node: &Option<Box<Node>>, target: i32) -> Option<&Box<Node>> {
    while let Some(n) = node {
        if n.value == target {
            return Some(n);
        }
        node = if target < n.value { &n.left } else { &n.right };
    }
    None
}

Insert#

How to insert a new value while maintaining the BST property:

Start at the root.
If less, go left; if greater, go right.
Repeat until you find a None/null spot.
Insert the new node there.

Recursive#

def insert(node, data):
    if node is None:
        return Node(data)
    else:
        if data < node.val:
            node.left = insert(node.left, data)
        elif data > node.val:
            node.right = insert(node.right, data)
    return node

python

function insert(node, data) {
  if (!node) {
    return new Node(data);
  }
  if (data < node.val) {
    node.left = insert(node.left, data);
  } else if (data > node.val) {
    node.right = insert(node.right, data);
  }
  return node;
}

func insert(node *Node, data int) *Node {
    if node == nil {
        return &Node{val: data}
    }
    if data < node.val {
        node.left = insert(node.left, data)
    } else if data > node.val {
        node.right = insert(node.right, data)
    }
    return node
}

public Node insert(Node node, int data) {
    if (node == null) {
        return new Node(data);
    }

    if (data < node.val) {
        node.left = insert(node.left, data);
    } else if (data > node.val) {
        node.right = insert(node.right, data);
    }

    return node;
}

java

public Node Insert(Node node, int data)
{
    if (node == null)
    {
        return new Node(data);
    }

    if (data < node.val)
    {
        node.left = Insert(node.left, data);
    }
    else if (data > node.val)
    {
        node.right = Insert(node.right, data);
    }

    return node;
}

Node* insert(Node* node, int data) {
    if (node == nullptr) {
        return new Node(data);
    }

    if (data < node->val) {
        node->left = insert(node->left, data);
    } else if (data > node->val) {
        node->right = insert(node->right, data);
    }

    return node;
}

cpp

Node* insert(Node* node, int key) {
    if (node == NULL) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->val = key;
        new_node->left = new_node->right = NULL;
        return new_node;
    }

    if (key < node->val) {
        node->left = insert(node->left, key);
    } else if (key > node->val) {
        node->right = insert(node->right, key);
    }

    return node;
}

impl Node {
    fn insert(&mut self, data: i32) {
        if data < self.val {
            match self.left {
                Some(ref mut left_child) => left_child.insert(data),
                None => self.left = Some(Box::new(Node { val: data, left: None, right: None })),
            }
        } else if data > self.val {
            match self.right {
                Some(ref mut right_child) => right_child.insert(data),
                None => self.right = Some(Box::new(Node { val: data, left: None, right: None })),
            }
        }
    }
}

Iterative#

Iterative BST insertion is possible but less common in practice. Recursive methods are clearer for most cases.

Iteration is used when the application is performance critical or the Binary Tree is deep enough it could cause a stack overflow.

def insert(node, data):
    if root is None:
        return Node(data)
    
    current = root
    while True:
        if data < current.val:
            if current.left is None:
                current.left = Node(data)
                break
            else:
                current = current.left
        elif data > current.val:
            if current.right is None:
                current.right = Node(data)
                break
            else:
                current = current.right
        else:
            break 
    
    return root

python

function insert(root, val) {
    if (root === null) {
        return new Node(val);
    }
    
    let current = root;
    while (true) {
        if (val < current.val) {
            if (current.left === null) {
                current.left = new Node(val);
                break;
            }
            current = current.left;
        } else if (val > current.val) {
            if (current.right === null) {
                current.right = new Node(val);
                break;
            }
            current = current.right;
        } else {
            break;
        }
    }
    return root;
}

func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{Val: val}
    }
    
    current := root
    for {
        if val < current.Val {
            if current.Left == nil {
                current.Left = &Node{Val: val}
                break
            }
            current = current.Left
        } else if val > current.Val {
            if current.Right == nil {
                current.Right = &Node{Val: val}
                break
            }
            current = current.Right
        } else {
            break
        }
    }
    return root
}

public Node insert(Node root, int val) {
    if (root == null) {
        return new Node(val);
    }
    
    Node current = root;
    while (true) {
        if (val < current.val) {
            if (current.left == null) {
                current.left = new Node(val);
                break;
            }
            current = current.left;
        } else if (val > current.val) {
            if (current.right == null) {
                current.right = new Node(val);
                break;
            }
            current = current.right;
        } else {
            break;
        }
    }
    return root;
}

java

public Node Insert(Node root, int val) {
    if (root == null) {
        return new Node(val);
    }
    
    Node current = root;
    while (true) {
        if (val < current.val) {
            if (current.left == null) {
                current.left = new Node(val);
                break;
            }
            current = current.left;
        } else if (val > current.val) {
            if (current.right == null) {
                current.right = new Node(val);
                break;
            }
            current = current.right;
        } else {
            break;
        }
    }
    return root;
}

java

Node* insert(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    
    Node* current = root;
    while (true) {
        if (val < current->val) {
            if (current->left == nullptr) {
                current->left = new Node(val);
                break;
            }
            current = current->left;
        } else if (val > current->val) {
            if (current->right == nullptr) {
                current->right = new Node(val);
                break;
            }
            current = current->right;
        } else {
            break;
        }
    }
    return root;
}

cpp

Node* insert(Node* root, int val) {
    if (root == NULL) {
        return createNode(val);
    }
    
    Node* current = root;
    while (1) {
        if (val < current->val) {
            if (current->left == NULL) {
                current->left = createNode(val);
                break;
            }
            current = current->left;
        } else if (val > current->val) {
            if (current->right == NULL) {
                current->right = createNode(val);
                break;
            }
            current = current->right;
        } else {
            break;
        }
    }
    return root;
}

pub fn insert(mut root: Option<Box<Node>>, val: i32) -> Option<Box<Node>> {
    let mut curr = &mut root;
    loop {
        match curr {
            None => {
                *curr = Some(Box::new(Node::new(val)));
                break;
            }
            Some(node) => {
                if val < node.val {
                    curr = &mut node.left;
                } else if val > node.val {
                    curr = &mut node.right;
                } else {
                    break;
                }
            }
        }
    }
    root
}

Delete#

Deleting a value from a BST is more involved:

If the node is a leaf: remove it.
If it has one child: replace it with its child.
If it has two children then you have two options:
- Replace it with its in-order successor (smallest node in right subtree)
- Replace it with its in-order predecessor (largest node in left subtree)
- After either of the above, remove the target node.

Deleting the node with value of 5

Recursive#

These examples cover every deletion case in a BST and use small, purpose built helpers for clarity. In real world code you can simplify further.

e.g. merge find_successor and find_predecessor into one function, or even inline that logic directly into your delete function if you don’t need the separate helpers.

def find_successor(node):
    current = node.right
    while current.left is not None:
        current = current.left
    return current

def find_predecessor(node):
    current = node.left
    while current.right is not None:
        current = current.right
    return current

def delete(root, target, use_successor=True):
    if root is None:
        return None

    if target < root.val:
        root.left = delete(root.left, target, use_successor)
    elif target > root.val:
        root.right = delete(root.right, target, use_successor)
    elif root.left is None and root.right is None:
        return None
    elif root.left is None:
        return root.right
    elif root.right is None:
        return root.left
    else:
        if use_successor:
            replacement = find_successor(root)
            root.val = replacement.val
            root.right = delete(root.right, replacement.val, use_successor)
        else:
            replacement = find_predecessor(root)
            root.val = replacement.val
            root.left = delete(root.left, replacement.val, use_successor)

    return root

python

function findSuccessor(node) {
  let current = node.right;
  while (current.left !== null) {
    current = current.left;
  }
  return current;
}

function findPredecessor(node) {
  let current = node.left;
  while (current.right !== null) {
    current = current.right;
  }
  return current;
}

function deleteNode(root, target, useSuccessor = true) {
  if (root === null) {
    return null;
  }

  if (target < root.val) {
    root.left = deleteNode(root.left, target, useSuccessor);
    return root;
  }
  if (target > root.val) {
    root.right = deleteNode(root.right, target, useSuccessor);
    return root;
  }

  switch (true) {
    case (root.left === null && root.right === null):
      return null;

    case (root.left === null):
      return root.right;

    case (root.right === null):
      return root.left;

    default:
      if (useSuccessor) {
        const replacement = findSuccessor(root);
        root.val = replacement.val;
        root.right = deleteNode(root.right, replacement.val, true);
      } else {
        const replacement = findPredecessor(root);
        root.val = replacement.val;
        root.left = deleteNode(root.left, replacement.val, false);
      }
      return root;
  }
}

func findSuccessor(node *Node) *Node {
	current := node.Right
	for current.Left != nil {
		current = current.Left
	}
	return current
}

func findPredecessor(node *Node) *Node {
	current := node.Left
	for current.Right != nil {
		current = current.Right
	}
	return current
}

func deleteNode(root *Node, target int, useSuccessor bool) *Node {
	if root == nil {
		return nil
	}
	if target < root.Val {
		root.Left = deleteNode(root.Left, target, useSuccessor)
	} else if target > root.Val {
		root.Right = deleteNode(root.Right, target, useSuccessor)
	} else {
		switch {
		case root.Left == nil && root.Right == nil:
			return nil
		case root.Left == nil:
			return root.Right
		case root.Right == nil:
			return root.Left
		default:
			if useSuccessor {
				repl := findSuccessor(root)
				root.Val = repl.Val
				root.Right = deleteNode(root.Right, repl.Val, useSuccessor)
			} else {
				repl := findPredecessor(root)
				root.Val = repl.Val
				root.Left = deleteNode(root.Left, repl.Val, useSuccessor)
			}
		}
	}
	return root
}

public Node findSuccessor(Node node) {
    Node current = node.right;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

public Node findPredecessor(Node node) {
    Node current = node.left;
    while (current.right != null) {
        current = current.right;
    }
    return current;
}

public Node deleteNode(Node root, int target, boolean useSuccessor) {
    if (root == null) {
        return root;
    }
    if (target < root.val) {
        root.left = deleteNode(root.left, target, useSuccessor);
    } else if (target > root.val) {
        root.right = deleteNode(root.right, target, useSuccessor);
    } else if (root.left == null && root.right == null) {
        return null;
    } else if (root.left == null) {
        return root.right;
    } else if (root.right == null) {
        return root.left;
    } else {
        if (useSuccessor) {
            Node replacement = findSuccessor(root);
            root.val = replacement.val;
            root.right = deleteNode(root.right, replacement.val, useSuccessor);
        } else {
            Node replacement = findPredecessor(root);
            root.val = replacement.val;
            root.left = deleteNode(root.left, replacement.val, useSuccessor);
        }
    }
    return root;
}

java

public Node FindSuccessor(Node node) {
    var current = node.right;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

public Node FindPredecessor(Node node) {
    var current = node.left;
    while (current.right != null) {
        current = current.right;
    }
    return current;
}

public Node DeleteNode(Node root, int target, bool useSuccessor = true) {
    if (root == null) {
        return root;
    }

    if (target < root.val) {
        root.left = DeleteNode(root.left, target, useSuccessor);
    } else if (target > root.val) {
        root.right = DeleteNode(root.right, target, useSuccessor);
    } else if (root.left == null && root.right == null) {
        return null;
    } else if (root.left == null) {
        return root.right;
    } else if (root.right == null) {
        return root.left;
    } else {
        if (useSuccessor) {
            var replacement = FindSuccessor(root);
            root.val = replacement.val;
            root.right = DeleteNode(root.right, replacement.val, useSuccessor);
        } else {
            var replacement = FindPredecessor(root);
            root.val = replacement.val;
            root.left = DeleteNode(root.left, replacement.val, useSuccessor);
        }
    }
    return root;
}

java

Node* findSuccessor(Node* node) {
    auto current = node->right;
    while (current->left) {
        current = current->left;
    }
    return current;
}

Node* findPredecessor(Node* node) {
    auto current = node->left;
    while (current->right) {
        current = current->right;
    }
    return current;
}

Node* deleteNode(Node* root, int target, bool useSuccessor = true) {
    if (!root) {
        return root;
    }

    if (target < root->val) {
        root->left = deleteNode(root->left, target, useSuccessor);
    } else if (target > root->val) {
        root->right = deleteNode(root->right, target, useSuccessor);
    } else if (!root->left && !root->right) {
        delete root;
        return nullptr;
    } else if (!root->left) {
        auto tmp = root->right;
        delete root;
        return tmp;
    } else if (!root->right) {
        auto tmp = root->left;
        delete root;
        return tmp;
    } else {
        if (useSuccessor) {
            auto replacement = findSuccessor(root);
            root->val = replacement->val;
            root->right = deleteNode(root->right, replacement->val, useSuccessor);
        } else {
            auto replacement = findPredecessor(root);
            root->val = replacement->val;
            root->left = deleteNode(root->left, replacement->val, useSuccessor);
        }
    }
    return root;
}

cpp


Node* findSuccessor(Node* node) {
    Node* current = node->right;
    while (current->left) {
        current = current->left;
    }
    return current;
}

Node* findPredecessor(Node* node) {
    Node* current = node->left;
    while (current->right) {
        current = current->right;
    }
    return current;
}

Node* deleteNode(Node* root, int target, int useSuccessor) {
    if (root == NULL) {
        return root;
    }
    if (target < root->val) {
        root->left = deleteNode(root->left, target, useSuccessor);
    } else if (target > root->val) {
        root->right = deleteNode(root->right, target, useSuccessor);
    } else if (!root->left && !root->right) {
        free(root);
        return NULL;
    } else if (!root->left) {
        Node* tmp = root->right;
        free(root);
        return tmp;
    } else if (!root->right) {
        Node* tmp = root->left;
        free(root);
        return tmp;
    } else {
        if (useSuccessor) {
            Node* replacement = findSuccessor(root);
            root->val = replacement->val;
            root->right = deleteNode(root->right, replacement->val, useSuccessor);
        } else {
            Node* replacement = findPredecessor(root);
            root->val = replacement->val;
            root->left = deleteNode(root->left, replacement->val, useSuccessor);
        }
    }
    return root;
}

fn find_successor(node: &Node) -> i32 {
    let mut cur = node;
    while let Some(ref left) = cur.left {
        cur = left;
    }
    cur.val
}

fn find_predecessor(node: &Node) -> i32 {
    let mut cur = node;
    while let Some(ref right) = cur.right {
        cur = right;
    }
    cur.val
}

pub fn delete_node(root: Option<Box<Node>>, target: i32, use_successor: bool) -> Option<Box<Node>> {
    match root {
        None => None,
        Some(mut node) => {
            if target < node.val {
                node.left = delete_node(node.left.take(), target, use_successor);
                Some(node)
            } else if target > node.val {
                node.right = delete_node(node.right.take(), target, use_successor);
                Some(node)
            } else {
                match (node.left.take(), node.right.take()) {
                    (None, None) => None,
                    (left, None) => left,
                    (None, right) => right,
                    (left, right) => {
                        let repl = if use_successor {
                            find_successor(&*right.as_ref().unwrap())
                        } else {
                            find_predecessor(&*left.as_ref().unwrap())
                        };
                        node.val = repl;
                        if use_successor {
                            node.right = delete_node(right, repl, true);
                            node.left = left;
                        } else {
                            node.left = delete_node(left, repl, false);
                            node.right = right;
                        }
                        Some(node)
                    }
                }
            }
        }
    }
}

Iterative#

Note that the helper functions now also return the current node and the parent node as a tuple.

def find_successor(node):
    current = node.right
    parent = node
    while current.left is not None:
        parent = current
        current = current.left
    return current, parent

def find_predecessor(node):
    current = node.left
    parent = node
    while current.right is not None:
        parent = current
        current = current.right
    return current, parent

def delete(root, key, use_successor=True):
    if root is None:
        return root

    parent = None
    current = root

    while current is not None and current.val != key:
        parent = current
        current = current.left if key < current.val else current.right

    if current is None:
        return root

    if current.left is None and current.right is None:
        if parent is None:
            return None  
        elif parent.left == current:
            parent.left = None
        else:
            parent.right = None

    elif current.left is None:
        if parent is None:
            return current.right
        elif parent.left == current:
            parent.left = current.right
        else:
            parent.right = current.right

    elif current.right is None:
        if parent is None:
            return current.left 
        elif parent.left == current:
            parent.left = current.left
        else:
            parent.right = current.left

    else:
        if use_successor:
            replacement, replacement_parent = find_successor(current)
        else:
            replacement, replacement_parent = find_predecessor(current)

        current.val = replacement.val

        if use_successor:
            if replacement_parent == current:
                replacement_parent.right = replacement.right
            else:
                replacement_parent.left = replacement.right
        elif replacement_parent == current:
            replacement_parent.left = replacement.left
        else:
            replacement_parent.right = replacement.left

    return root

python

function findSuccessor(node) {
    let current = node.right;
    let parent = node;
    while (current.left !== null) {
        parent = current;
        current = current.left;
    }
    return [current, parent];
}

function findPredecessor(node) {
    let current = node.left;
    let parent = node;
    while (current.right !== null) {
        parent = current;
        current = current.right;
    }
    return [current, parent];
}

function deleteNode(root, key, useSuccessor = true) {
    if (root === null) {
      return root;
    }

    let parent  = null;
    let current = root;
    
    while (current !== null && current.val !== key) {
        parent  = current;
        current = key < current.val ? current.left : current.right;
    }
    if (current === null) {
        return root;
    }

    switch (true) {
      case (current.left === null && current.right === null):
        if (parent === null) {
          root = null;
        } else if (parent.left === current) {
          parent.left = null;
        } else {
          parent.right = null;
        }
        break;

      case (current.left === null):
        if (parent === null) {
          root = current.right;
        } else if (parent.left === current) {
          parent.left = current.right;
        } else {
          parent.right = current.right;
        }
        break;

      case (current.right === null):
        if (parent === null) {
          root = current.left;
        } else if (parent.left === current) {
          parent.left = current.left;
        } else {
          parent.right = current.left;
        }
        break;

      default: {
        const [replacement, replacementParent] = useSuccessor
          ? findSuccessor(current)
          : findPredecessor(current);

        current.val = replacement.val;

        if (useSuccessor) {
          if (replacementParent === current) {
            replacementParent.right = replacement.right;
          } else {
            replacementParent.left =  replacement.right;
          }
        } else {
          if (replacementParent === current) {
            replacementParent.left = replacement.left;
          } else {
            replacementParent.right = replacement.left;
          }
        }
      }
    }

    return root;
}

func findSuccessor(node *Node) (*Node, *Node) {
    current := node.Right
    parent := node
    for current.Left != nil {
        parent = current
        current = current.Left
    }
    return current, parent
}

func findPredecessor(node *Node) (*Node, *Node) {
    current := node.Left
    parent := node
    for current.Right != nil {
        parent = current
        current = current.Right
    }
    return current, parent
}

func deleteNode(root *Node, key int, useSuccessor bool) *Node {
	if root == nil {
		return nil
	}

	var parent *Node
	current := root
	for current != nil && current.Val != key {
		parent = current
		if key < current.Val {
			current = current.Left
		} else {
			current = current.Right
		}
	}

	if current == nil {
		return root
	}

	switch {
	case current.Left == nil && current.Right == nil:
		if parent == nil {
			return nil
		} else if parent.Left == current {
			parent.Left = nil
		} else {
			parent.Right = nil
		}

	case current.Left == nil:
		if parent == nil {
			return current.Right
		} else if parent.Left == current {
			parent.Left = current.Right
		} else {
			parent.Right = current.Right
		}

	case current.Right == nil:
		if parent == nil {
			return current.Left
		} else if parent.Left == current {
			parent.Left = current.Left
		} else {
			parent.Right = current.Left
		}

	default:
		var repl, replParent *Node
		if useSuccessor {
			repl, replParent = findSuccessor(current)
		} else {
			repl, replParent = findPredecessor(current)
		}
		current.Val = repl.Val

		if useSuccessor {
			if replParent == current {
				replParent.Right = repl.Right
			} else {
				replParent.Left = repl.Right
			}
		} else {
			if replParent == current {
				replParent.Left = repl.Left
			} else {
				replParent.Right = repl.Left
			}
		}
	}

	return root
}

class NodeParentPair {
    Node node;
    Node parent;
    
    NodeParentPair(Node node, Node parent) {
        this.node = node;
        this.parent = parent;
    }
}

public class BSTDeletion {
    
    public static NodeParentPair findSuccessor(Node node) {
        Node current = node.right;
        Node parent = node;
        while (current.left != null) {
            parent = current;
            current = current.left;
        }
        return new NodeParentPair(current, parent);
    }
    
    public static NodeParentPair findPredecessor(Node node) {
        Node current = node.left;
        Node parent = node;
        while (current.right != null) {
            parent = current;
            current = current.right;
        }
        return new NodeParentPair(current, parent);
    }
    
    public static Node deleteNode(Node root, int key, boolean useSuccessor) {
        if (root == null) {
            return root;
        }
        
        Node parent = null;
        Node current = root;
        
        while (current != null && current.val != key) {
            parent = current;
            current = key < current.val ? current.left : current.right;
        }
        
        if (current == null) {
            return root;
        }
        
        if (current.left == null && current.right == null) {
            if (parent == null) {
                return null;
            } else if (parent.left == current) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        else if (current.left == null) {
            if (parent == null) {
                return current.right;
            } else if (parent.left == current) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }
        else if (current.right == null) {
            if (parent == null) {
                return current.left;
            } else if (parent.left == current) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        }
        else {
            NodeParentPair replacementPair;
            if (useSuccessor) {
                replacementPair = findSuccessor(current);
            } else {
                replacementPair = findPredecessor(current);
            }
            
            Node replacement = replacementPair.node;
            Node replacementParent = replacementPair.parent;
            
            current.val = replacement.val;
            
            if (useSuccessor) {
                if (replacementParent == current) {
                    replacementParent.right = replacement.right;
                } else {
                    replacementParent.left = replacement.right;
                }
            } else {
                if (replacementParent == current) {
                    replacementParent.left = replacement.left;
                } else {
                    replacementParent.right = replacement.left;
                }
            }
        }
        
        return root;
    }
}

java

public class NodeParentPair 
{
    public Node Node { get; set; }
    public Node Parent { get; set; }
    
    public NodeParentPair(Node node, Node parent) 
    {
        Node = node;
        Parent = parent;
    }
}

public class BSTDeletion 
{
    public static NodeParentPair FindSuccessor(Node node) 
    {
        Node current = node.right;
        Node parent = node;
        while (current.left != null) 
        {
            parent = current;
            current = current.left;
        }
        return new NodeParentPair(current, parent);
    }
    
    public static NodeParentPair FindPredecessor(Node node) 
    {
        Node current = node.left;
        Node parent = node;
        while (current.right != null) 
        {
            parent = current;
            current = current.right;
        }
        return new NodeParentPair(current, parent);
    }
    
    public static Node DeleteNode(Node root, int key, bool useSuccessor = true) 
    {
        if (root == null) 
        {
            return root;
        }
        
        Node parent = null;
        Node current = root;
        
        while (current != null && current.val != key) 
        {
            parent = current;
            current = key < current.val ? current.left : current.right;
        }
        
        if (current == null) 
        {
            return root;
        }
        
        if (current.left == null && current.right == null) 
        {
            if (parent == null) 
            {
                return null;
            } 
            else if (parent.left == current) 
            {
                parent.left = null;
            } 
            else 
            {
                parent.right = null;
            }
        }
        else if (current.left == null) 
        {
            if (parent == null) 
            {
                return current.right;
            } 
            else if (parent.left == current) 
            {
                parent.left = current.right;
            } 
            else 
            {
                parent.right = current.right;
            }
        }
        else if (current.right == null) 
        {
            if (parent == null) 
            {
                return current.left;
            } 
            else if (parent.left == current) 
            {
                parent.left = current.left;
            } 
            else 
            {
                parent.right = current.left;
            }
        }
        else 
        {
            NodeParentPair replacementPair;
            if (useSuccessor) 
            {
                replacementPair = FindSuccessor(current);
            } 
            else 
            {
                replacementPair = FindPredecessor(current);
            }
            
            Node replacement = replacementPair.Node;
            Node replacementParent = replacementPair.Parent;
            
            current.val = replacement.val;
            
            if (useSuccessor) 
            {
                if (replacementParent == current) 
                {
                    replacementParent.right = replacement.right;
                } 
                else 
                {
                    replacementParent.left = replacement.right;
                }
            } 
            else 
            {
                if (replacementParent == current) 
                {
                    replacementParent.left = replacement.left;
                } 
                else 
                {
                    replacementParent.right = replacement.left;
                }
            }
        }
        
        return root;
    }
}

std::pair<Node*, Node*> findSuccessor(Node* node) {
    Node* current = node->right;
    Node* parent = node;
    while (current->left != nullptr) {
        parent = current;
        current = current->left;
    }
    return std::make_pair(current, parent);
}

std::pair<Node*, Node*> findPredecessor(Node* node) {
    Node* current = node->left;
    Node* parent = node;
    while (current->right != nullptr) {
        parent = current;
        current = current->right;
    }
    return std::make_pair(current, parent);
}

Node* deleteNode(Node* root, int key, bool useSuccessor = true) {
    if (root == nullptr) {
        return root;
    }
    
    Node* parent = nullptr;
    Node* current = root;
    
    while (current != nullptr && current->val != key) {
        parent = current;
        current = key < current->val ? current->left : current->right;
    }
    
    if (current == nullptr) {
        return root;
    }
    
    if (current->left == nullptr && current->right == nullptr) {
        if (parent == nullptr) {
            delete current;
            return nullptr;
        } else if (parent->left == current) {
            parent->left = nullptr;
        } else {
            parent->right = nullptr;
        }
        delete current;
    }
    else if (current->left == nullptr) {
        Node* rightChild = current->right;
        if (parent == nullptr) {
            delete current;
            return rightChild;
        } else if (parent->left == current) {
            parent->left = rightChild;
        } else {
            parent->right = rightChild;
        }
        delete current;
    }
    else if (current->right == nullptr) {
        Node* leftChild = current->left;
        if (parent == nullptr) {
            delete current;
            return leftChild;
        } else if (parent->left == current) {
            parent->left = leftChild;
        } else {
            parent->right = leftChild;
        }
        delete current;
    }
    else {
        std::pair<Node*, Node*> replacementPair;
        if (useSuccessor) {
            replacementPair = findSuccessor(current);
        } else {
            replacementPair = findPredecessor(current);
        }
        
        Node* replacement = replacementPair.first;
        Node* replacementParent = replacementPair.second;
        
        current->val = replacement->val;
        
        if (useSuccessor) {
            if (replacementParent == current) {
                replacementParent->right = replacement->right;
            } else {
                replacementParent->left = replacement->right;
            }
        } else {
            if (replacementParent == current) {
                replacementParent->left = replacement->left;
            } else {
                replacementParent->right = replacement->left;
            }
        }
        delete replacement;
    }
    
    return root;
}

cpp

NodeParentPair findSuccessor(Node* node) {
    Node* current = node->right;
    Node* parent = node;
    while (current->left != NULL) {
        parent = current;
        current = current->left;
    }
    NodeParentPair pair = {current, parent};
    return pair;
}

NodeParentPair findPredecessor(Node* node) {
    Node* current = node->left;
    Node* parent = node;
    while (current->right != NULL) {
        parent = current;
        current = current->right;
    }
    NodeParentPair pair = {current, parent};
    return pair;
}

Node* deleteNode(Node* root, int key, bool useSuccessor) {
    if (root == NULL) {
        return root;
    }
    
    Node* parent = NULL;
    Node* current = root;
    
    while (current != NULL && current->val != key) {
        parent = current;
        current = key < current->val ? current->left : current->right;
    }
    
    if (current == NULL) {
        return root;
    }

    if (current->left == NULL && current->right == NULL) {
        if (parent == NULL) {
            free(current);
            return NULL;
        } else if (parent->left == current) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
        free(current);
    }
    else if (current->left == NULL) {
        Node* rightChild = current->right;
        if (parent == NULL) {
            free(current);
            return rightChild;
        } else if (parent->left == current) {
            parent->left = rightChild;
        } else {
            parent->right = rightChild;
        }
        free(current);
    }
    else if (current->right == NULL) {
        Node* leftChild = current->left;
        if (parent == NULL) {
            free(current);
            return leftChild;
        } else if (parent->left == current) {
            parent->left = leftChild;
        } else {
            parent->right = leftChild;
        }
        free(current);
    }
    else {
        NodeParentPair replacementPair;
        if (useSuccessor) {
            replacementPair = findSuccessor(current);
        } else {
            replacementPair = findPredecessor(current);
        }
        
        Node* replacement = replacementPair.node;
        Node* replacementParent = replacementPair.parent;
        
        current->val = replacement->val;
        
        if (useSuccessor) {
            if (replacementParent == current) {
                replacementParent->right = replacement->right;
            } else {
                replacementParent->left = replacement->right;
            }
        } else {
            if (replacementParent == current) {
                replacementParent->left = replacement->left;
            } else {
                replacementParent->right = replacement->left;
            }
        }
        free(replacement);
    }
    
    return root;
}

void freeTree(Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

fn remove_successor(node: &mut Node) -> i32 {
    if let Some(mut right) = node.right.take() {
        if right.left.is_none() {
            let val = right.val;
            node.right = right.right.take();
            val
        } else {
            let mut current = &mut right;
            while current.left.as_ref().unwrap().left.is_some() {
                current = current.left.as_mut().unwrap();
            }
            let mut successor = current.left.take().unwrap();
            let val = successor.val;
            current.left = successor.right.take();
            node.right = Some(right);
            val
        }
    } else {
        node.val
    }
}

fn remove_predecessor(node: &mut Node) -> i32 {
    if let Some(mut left) = node.left.take() {
        if left.right.is_none() {
            let val = left.val;
            node.left = left.left.take();
            val
        } else {
            let mut current = &mut left;
            while current.right.as_ref().unwrap().right.is_some() {
                current = current.right.as_mut().unwrap();
            }
            let mut predecessor = current.right.take().unwrap();
            let val = predecessor.val;
            current.right = predecessor.left.take();
            node.left = Some(left);
            val
        }
    } else {
        node.val
    }
}

pub fn delete_node(root: Option<Box<Node>>, key: i32, use_successor: bool) -> Option<Box<Node>> {
    let mut root = root?;
    
    if root.val == key {
        return match (&root.left, &root.right) {
            (None, None) => None,
            (Some(_), None) => root.left.take(),
            (None, Some(_)) => root.right.take(),
            (Some(_), Some(_)) => {
                if use_successor {
                    root.val = remove_successor(&mut root);
                } else {
                    root.val = remove_predecessor(&mut root);
                }
                Some(root)
            }
        };
    }
    
    let mut current = &mut root;
    loop {
        let go_left = key < current.val;
        let target = if go_left { &mut current.left } else { &mut current.right };
        
        match target {
            None => return Some(root),
            Some(node) if node.val == key => {
                match (&node.left, &node.right) {
                    (None, None) => {
                        *target = None;
                    }
                    (Some(_), None) => {
                        *target = node.left.take();
                    }
                    (None, Some(_)) => {
                        *target = node.right.take();
                    }
                    (Some(_), Some(_)) => {
                        if use_successor {
                            node.val = remove_successor(node);
                        } else {
                            node.val = remove_predecessor(node);
                        }
                    }
                }
                break;
            }
            Some(node) => {
                current = node;
            }
        }
    }
    
    Some(root)
}

Time Complexity#

For any BST operation (search, insert, delete), the time complexity is O(h) where h is the tree’s height.

Tree Structure	Height (h)	Time Complexity	Example
Balanced	O(log n)	O(log n)	Perfect binary tree
Unbalanced	O(n)	O(n)	Linked list structure / skewed

Balanced Trees (Best Case)#

Height approximately log₂ n
Performance: O(log n) for all operations
Example: With 1,000 nodes, height ≈ 10 levels

Skewed Trees (Worst Case)#

Height equals n (essentially a linked list)
Performance: O(n) for all operations
Example: Inserting sorted data: 1→2→3→4→5

Space Complexity#

Implementation	Space Complexity	Notes
Recursive	O(h)	Call stack grows with height
Iterative	O(1)	Constant extra space

Why Balancing Matters#

Without balancing:

Sorted input creates O(n) height
Performance degrades to linear search
Defeats the purpose of using a BST

With self-balancing (AVL, Red-Black):

Automatic rotations maintain O(log n) height
Guaranteed logarithmic performance
Slight overhead for rebalancing operations

Common Pitfalls#

Inserting sorted data leads to an unbalanced, degenerate tree (poor performance).
BST property violations can occur with incorrect insert/delete logic.
Duplicate values: handle as per requirements (left/right, or disallow).
Memory leaks in C/C++ when forgetting to free deleted nodes.
Parent pointer management errors during deletion (especially with two children).
Edge case bugs: deleting root node, single-node trees, or non-existent keys.
Mixing recursive/iterative approaches inconsistently in the same codebase.
Assuming balanced performance without using self-balancing variants.

Summary#

Best Practice: Use self-balancing BSTs (AVL, Red-Black) for guaranteed O(log n) performance.
Height Determines Performance: All BST operations are O(h); balanced trees ensure optimal performance.
Iterative vs. Recursive:
- Recursive approaches are simpler and easier to understand, suitable when height (h) is guaranteed to be O(log n).
- Iterative approaches can optimize space complexity O(1), beneficial when height could be large (potentially O(n)) or in memory-constrained environments.

What’s Next#

In Post 4: Self-Balancing Trees - AVL & Red-Black, we’ll build on our BST foundations to see:

Rotations (left & right) step by step
Invariants that distinguish AVL vs. Red-Black trees
When to pick which structure for your use case