Language: EN FI

Exercises > Binary Search Tree Deletion

These exercises demonstrate the content of the ByTheMark service. These are meant for private individuals for learning data structures and algorithms. If you want to try out more content, you can register to the ByTheMark Personal free of charge.

Delete the given keys one at a time from the binary search tree. Possible equal keys were inserted into the left branch of the existing node. Please note that the insertion strategy also affects how the deletion is performed.

Node Delete(Node root, Key k)
1  if (root == null) // failed search
2    return null;
3  if (k == root.key) // successful search
4    return DeleteThis(root);
5  if (k < root.key) // k in the left branch
6    root.left = Delete(root.left, k);
7  else // k > root.key, i.e., k in the right branch
8    root.right = Delete(root.right, k);
9  return root;

Node DeleteThis(Node root)
1  if root has two children
2    p = Largest(root.left); // replace root with its immediate predecessor p
3    root.key = p.key;
4    root.left = Delete(root.left, p)
5    return root;
6  if root has only left child
7    return root.left
8  if root has only right child
9    return root.right
10  else root has no children
11   return null

Node Largest(Node root)
1  if root has no right child
2    return root
3  return Largest(root.right)

  Last modified Tue Mar 01 20:54:04 EET 2011