Exercices: Binary search tree exercices

Duration of the supervised session1h15

Below is a list of exercises for experimenting with building algorithms focusing on binary search tree.

Exercice 1: Implement tree_insert for a Binary Search Tree

Write a function tree_insert(root, key) that inserts a node with the given key into a Binary Search Tree (BST) while maintaining the BST property. The goal is to use the tree_insert to recursively construct a BST on the following sequence [10, 5, 7, 4, 9].

from binarytree import tree, bst, heap, Node

def tree_insert(root, key):
    # Create the new node
    z = Node(key)
    y = None
    x = root

    # Find the correct position for the new node
    while x is not None:
        y = x
        if z.value < x.value:
            x = x.left
        else:
            x = x.right

    # Insert the new node
    if y is None:
        root = z  # The tree was empty
    elif z.value < y.value:
        y.left = z
    else:
        y.right = z

    return root



values = [0]
values_to_store = [10, 5, 7, 4, 9]
my_bst = build(values)
print(my_bst)
for i in range(len(values_to_store)):
    key = values_to_store[i]
    my_bst = tree_insert(my_bst, key)
print(my_bst)

Exercice 2: Tree-Successor

Exercice 3: Implement tree_delete for a Binary Search Tree

Write a function tree_delete(root, key) that remove a node with the given key into a Binary Search Tree (BST) while maintaining the BST property.

The algorithm for deleting a node with a given key considers three cases:

1. If the node associated to search key has no children then we modify its parent to replace the node with NIL;

2. If the node has only a single child, we remove the node and we make a new link between its children and its parents.

3. If the node has only two children, then the procedure is more complex.

   First we need the following definition: The inorder successor of a node in a binary search tree (BST) is the node with the smallest key greater than the key of the given node.

   • Replace the content of the node by its inorder successor;
   • Delete the inorder successor;
   • Add a new link between inorder successor children and inorder successor parents.

You can test you algorithm on your previously constructed tree.