Removing Root Node in Binary Search Tree

Question

I'm currently unable to delete the root node of my binary search tree in these situations

1. the root node doesn't have a left attribute or doesn't have a right attribute

2. the root has neither attribute (leaf)

from __future__ import annotations

from collections.abc import Iterator
from typing import Any, Optional


class TreeNode:
    def __init__(self, value: Any, left: BST, right: BST):
        self.value = value
        self.left = left
        self.right = right

    def __repr__(self):
        return f"TreeNode({self.value}, {self.left}, {self.right})"

    def __eq__(self, other):
        return self.value == other.value and \
            self.right == other.right and self.left == other.left


BST = Optional[TreeNode]


def is_empty(tree: BST) -> bool:
    """Return True if the tree is empty, False otherwise."""
    return tree is None  # check if BST input is none (empty)


def search(tree: BST, value: Any) -> bool:
    """Return True if value is in tree, False otherwise."""
    if tree is None:
        return False
    else:
        return (
            tree.value == value
            or search(tree.left, value)
            or search(tree.right, value)
        )


def insert(tree: BST, value: Any) -> BST:
    """Insert the value into the tree in the proper location."""
    if tree is None:
        return TreeNode(value, None, None)
    elif tree.value is None:
        tree.value = value
    elif value > tree.value:
        if tree.right is None:
            tree.right = TreeNode(value, None, None)
        return insert(tree.right, value)
    elif value < tree.value:
        if tree.left is None:
            tree.left = TreeNode(value, None, None)
        return insert(tree.left, value)


def delete(tree: BST, value: Any) -> BST:
    """Remove the value from the tree (if present).

    If the value is not present, this function does nothing.
    """
    try:
        root = (tree.value,)
        print(root[0])
    finally:
        pass

    if tree is None:
        return tree

    elif value < tree.value:
        tree.left = delete(tree.left, value)

    elif value > tree.value:

        tree.right = delete(tree.right, value)
    else:
        if tree.left is None and tree.right is None:  # No children
            if tree.value == root[0]:
                tree.value = None
            return tree
        elif tree.left is not None and tree.right is not None:  # Two children
            replacement = tree.right
            while replacement.left is not None:  # Find smallest "big" value
                replacement = replacement.left
            tree.value = replacement.value  # Set value to smallest "big" value
            tree.right = delete(tree.right, replacement.value)  # Delete value
        else:  # One child
            if tree.left is not None:  # Promote left child
                return tree.left
            else:
                return tree.left
    return tree

I'm struggling to delete the root of my BST when one of its left/right components is empty or if both components are empty. Did you guys keep track of your root value throughout your function? I tried implementing a tuple to save keep my root Node, however, my implementation is still running into errors. 

Answer 1

First of all, you have some code that gives a special meaning to the value None in the root node. This is not how it should be done. Your is_empty function is right: a tree is empty only when the tree reference itself is None, not when the root's value happens to be None.

So remove this logic (concerning tree.value is None) from your insert and delete functions. And in your main program, initialise your tree as None, not as TreeNode(None).

Insert

There are some bugs in insert:

• In the value > tree.value block, when tree.right is None, your code creates a new node, and then still makes a recursive call to insert a node. This is not right. In fact, you should not create a node here at all, but completely rely on the recursive call, which will do that when it gets a None as argument.

• In this same block, you should not return what insert() returns, which is right subtree. Instead you should assign that return value to tree.right and then return tree

• In case none of the if blocks is entered (which happens when the value is already in the tree), you should still return tree.

Here is a correction for insert:

def insert(tree: BST, value: Any) -> BST:
    """Insert the value into the tree in the proper location."""
    if tree is None:
        return TreeNode(value, None, None)
    if value > tree.value:
        tree.right = insert(tree.right, value)  # correction
    elif value < tree.value:
        tree.left = insert(tree.left, value)  # correction
    return tree # missing: must always return BST type

Delete

There are these issues in the delete function:

• There is a trivial bug near the end of the function where you do return tree.left in both cases. One of those should be return tree.right.

• In the case the node is a leaf you should not return tree, but None as that will serve for the caller to actually detach that node.

• Not a problem, but the case where there are no children does not need a separate treatment. The code that deals with the 1-child case can also deal with the 0-children case.

Here is a correction for delete:

def delete(tree: BST, value: Any) -> BST:
    """Remove the value from the tree (if present).

    If the value is not present, this function does nothing.
    """
    if tree is None:
        return tree
    elif value < tree.value:
        tree.left = delete(tree.left, value)
    elif value > tree.value:
        tree.right = delete(tree.right, value)
    elif tree.left and tree.right: # Has two children
        replacement = tree.right
        while replacement.left is not None:  # Find smallest "big" value
            replacement = replacement.left
        tree.value = replacement.value  # Set value to smallest "big" value
        tree.right = delete(tree.right, replacement.value)  # Delete value
    else:  # Zero or one child (same treatment)
        return tree.left or tree.right  # shorter notation to promote a child
    return tree

Main program

There was no main program included in your code, so I will provide one here. It includes:

• A utility function to display a tree in a 90° rotated way (with root pictured at the left side), using indentation to indicate depth.

• Code that populates a tree.

  Note that the tree starts as None (empty) and that the return value of insert is always assigned back to tree.

• Code that deletes some nodes from this tree.

  Note again that the return value of delete is always assigned back to tree.

def display(tree: BST, tab: str=""):
    if tree:
        display(tree.right, tab + "  ")
        print(tab, tree.value)
        display(tree.left, tab + "  ")
    

tree: BST = None  # This is an empty tree
for value in (4, 2, 6, 1, 3, 5, 7):
    tree = insert(tree, value)
print("populated BST:")
display(tree)

for value in (6,9,1,4):
    print("delete", value)
    tree = delete(tree, value)
    display(tree)

This demo program will produce this output:

populated BST:
     7
   6
     5
 4
     3
   2
     1
delete 6
   7
     5
 4
     3
   2
     1
delete 9
   7
     5
 4
     3
   2
     1
delete 1
   7
     5
 4
     3
   2
delete 4
   7
 5
     3
   2