Data Structures for Coding Interviews in Python/

...

/

Deletion in a Binary Search Tree (Implementation)

Deletion in a Binary Search Tree (Implementation)

We will now write the implementation of the deletion function which covers all the cases that we discussed previously.

We'll cover the following...

Introduction #

Let’s implement the delete function for BSTs. We’ll build upon the code as we cater for each case.

Also, note that the delete function in the BinarySearchTree class is simply calling the delete function in the Node class where the core of our implementation will reside.

1. Deleting an Empty Tree #

Let’s start with a skeleton function definition and cater for the first case. If the root does not exist, we return False in the BinarySearchTree class.

Python 3.5
from Node import Node
from BinarySearchTree import BinarySearchTree
import random
def display(node):
    lines, _, _, _ = _display_aux(node)
    for line in lines:
        print(line)
def _display_aux(node):
    """
    Returns list of strings, width, height,
    and horizontal coordinate of the root.
    """
    # None.
    if node is None:
        line = 'Empty tree!'
        width = len(line)
        height = 1
        middle = width // 2
        return [line], width, height, middle
    # No child.
    if node.rightChild is None and node.leftChild is None:
        line = str(node.val)
        width = len(line)
        height = 1
        middle = width // 2
        return [line], width, height, middle
    # Only left child.
    if node.rightChild is None:
        lines, n, p, x = _display_aux(node.leftChild)
        s = str(node.val)
        u = len(s)
        first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
        second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
        shifted_lines = [line + u * ' ' for line in lines]
        final_lines = [first_line, second_line] + shifted_lines
        return final_lines, n + u, p + 2, n + u // 2
    # Only right child.
    if node.leftChild is None:
        lines, n, p, x = _display_aux(node.rightChild)
        s = str(node.val)
        u = len(s)
#        first_line = s + x * '_' + (n - x) * ' '
        first_line = s + x * '_' + (n - x) * ' '
        second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
        shifted_lines = [u * ' ' + line for line in lines]
        final_lines = [first_line, second_line] + shifted_lines
        return final_lines, n + u, p + 2, u // 2
    # Two children.
    left, n, p, x = _display_aux(node.leftChild)
    right, m, q, y = _display_aux(node.rightChild)
    s = '%s' % node.val
    u = len(s)
    first_line = (x + 1) * ' ' + (n - x - 1) * \
        '_' + s + y * '_' + (m - y) * ' '
    second_line = x * ' ' + '/' + \
        (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
    if p < q:
        left += [n * ' '] * (q - p)
    elif q < p:
        right += [m * ' '] * (p - q)
    zipped_lines = zip(left, right)
    lines = [first_line, second_line] + \
        [a + u * ' ' + b for a, b in zipped_lines]
    return lines, n + m + u, max(p, q) + 2, n + u // 2
BST = BinarySearchTree(50)
print("tree:")
display(BST.root)
BST.delete(50)
BST.delete(50)  # Deleting in an empty tree
display(BST.root)

Searching for val

...