Binary Search Tree - My own version of delete function

Question

Well, I am recently learning data structures and algorithms and I came across the Binary search tree and decided to first time use my own logic to make the delete function. I have not come across a code similar to mine in the delete function, although it is possible someone already used this logic, please share if you find any. I have tried as simply as I can to explain my logic in comments and docstrings for others to understand. try using code preview plugins or use the https://pythontutor.com/visualize.html#mode=edit website to visualize the rotation because this is the most complex logic I have ever created. My goal was to make a delete function in BST in the least line of code as possible as I have seen people using over 14 if statements for this function. In my logic, I replaced the node that I want to delete with its right child node or replaces it with left node if it only has left child node or if it has no child it will recursively look for the node and delete it. I have explained it in the code as well. I welcome constructive criticism and if someone can improve it please feel free to do that as well. I have tested it so far by inserting numbers randomly and also using large input data as well. So far the code is working. I will be waiting for your feedback, thank you. The code is as follows:

class BST:
def __init__(self, data):
    """This is a constructor

    Args:
        data (integer): This is the main root node of binary search tree
        self.lchild (integer): This is the left child node
        self.rchild (integer): This is the Right child node
    """
    self.root = data
    self.lchild = None
    self.rchild = None

def insert(self, data):
    """This is an insert function which is using recursion to insert new nodes into there
    respective places.

    Args:
        data (integer): This is a node
    """
    # if root node is None insert the node
    if not self.root:
        self.root = data

    # we are ignore the duplicate values by just returning the function here
    if self.root == data:
        return

    else:
        if data < self.root:
            # we are caling the function recursively here to create instances of nodes
            if self.lchild:
                self.lchild.insert(data)

            else:
                # creating an object inside the left hand side of the tree
                self.lchild = BST(data)

        else:
            if self.rchild:
                self.rchild.insert(data)

            else:
                # creating an object inside the right hand side of the tree
                self.rchild = BST(data)

def search(self, data):
    """This is a search function to find the desired node again using same recursive technique
    that we used in insert

    Args:
        data (integer): The numbder that you want to search
    """
    if data == self.root:
        print(f"number {self.root} is found ")

    else:
        if data < self.root:
            if self.lchild:
                self.lchild.search(data)

            else:
                print(f"number not found")

        else:
            if self.rchild:
                self.rchild.search(data)

            else:
                print(f"number not found")

def preorder(self):
    """This function will print all the nodes in pre order, in this root node comes first
    then left child and right child.
    """
    print(self.root)

    if self.lchild:
        self.lchild.preorder()

    if self.rchild:
        self.rchild.preorder()

def in_order(self):
    """This function will print all the nodes in sequence, first comes the smallest node
    and then root node and then all the larger numbers than root node.
    """
    if self.lchild:
        self.lchild.in_order()

    print(self.root)

    if self.rchild:
        self.rchild.in_order()

def del_node(self, data):
    """This is a delete function to delete the node from the tree, this function is using the logic
    in which we always replace the node we are going to delete with the right child of that node,
    if it has one. otherwise with the left child node or if it do not have any child nodes then
    simply delete the node.

    Args:
        data (integer): The node we want to delete
    """

    if data == self.root:
        if self.rchild:
            self.root = (
                self.rchild.root
            )  # we are replacing the root node with its right child node (self.rchild.root)
            self.rchild = (
                self.rchild.rchild
            )  # here we are replacing the right node with the right node of the instance
            # we want to delete(I know it sounds complex but could not find a more simpler way to explain it)

        elif self.lchild:
            self.root = (
                self.lchild.root
            )  # same logic that we did with right child node in case ifit do not have a right child
            self.lchild = self.lchild.lchild

    else:
        # using recursion here to keep traveling through nodes until it finds the node that we want
        # to delete and print "data not found" if node is not present in the tree.
        if data < self.root:
            if self.lchild:
                self.lchild.del_node(data)

                # if the node that i want to delete have no child nodes this if statement will excute on all the instances where it traveled through to find the node that I wanted to delete
                if data == self.lchild.root:
                    self.lchild = None

            else:
                print("data not found")

        else:
            if self.rchild:
                self.rchild.del_node(data)

                # if the node that i want to delete have no child nodes this if statement will excute on all the instances where it traveled through to find the node that I wanted to delete
                if data == self.rchild.root:
                    self.rchild = None

            else:
                print("data not found")

Answer 1

Address more fundamental issues before worrying about delete

A BST should be able to hold false values. For example, zero. Instead of if not self.root, use if self.value is not None. [In this review I adopt the suggested renaming, changing root to value, and I extend the idea by changing data to val.]

Adopt a consistent naming convention. You have preorder() but not inorder(). You have insert() but not delete().

An empty BST should be possible. Currently, your __init__() method doesn't support the most basic of behaviors: a user should be able to do this: b = BST().

Data oriented classes should return data, not print. The search() method should return a boolean; preorder() and inorder() methods should return or yield values.

A BST should not allow a value of None. A ValueError should be raised if the caller tries to insert or search for None.

The code is needlessly repetitive. In most cases, this occurs because you write nearly equivalent code for the left and right sides. But that repetition can be eliminated with just a little bit of generalization.

A BST should be able to hold lots of data. Because you are using recursion, you will quickly run up against Python's maximum recursion depth (1000 by default). Iteration is a better strategy for a BST. For example, here are search() and insert() rewritten with the foregoing suggestions in mind. I would encourage you to apply similar edits to the rest of the class, including delete().

def search(self, val):
    if val is None:
        raise ValueError('BST cannot hold None')
    tree = self
    while True:
        if tree is None or tree.value is None:
            return False
        elif val == tree.value:
            return True
        else:
            tree = tree.lchild if val < tree.value else tree.rchild

def insert(self, val):
    if val is None:
        raise ValueError('BST cannot hold None')
    tree = self
    while True:
        if tree.value is None:
            tree.value = val
            return
        elif val == tree.value:
            return
        elif val != tree.value:
            attr = 'lchild' if val < tree.value else 'rchild'
            child = getattr(tree, attr, None)
            if child:
                tree = child
            else:
                setattr(tree, attr, BST(val))
                return

Answer 2

Naming

The BST's property root is misleading, since it does not store a reference to the root element of the tree, but the node's value. Hence it should be named value.

Generalization and type hinting

You limit your BST to int as per your comments. Why? You can introduce a TypeVar to allow for arbitrary types.

from typing import Protocol, TypeVar


class Comparable(Protocol):
    """Comparable type."""
        
    def __eq__(self):
        ...
    
    def __lt__(self):
        ...

T = TypeVar('T', bound=Comparable)


class BST:
    def __init__(self, value: T):
        """Initialize a BST element with the given value."""
        self.value = value
        self.lchild = None
        self.rchild = None

    ...

As shown above and below, it would also be a good idea to use type hints, so that the user of the datastructure can see which values are expected and returned.

Useless nested else

Using else after a return is useless. Furthermore you should consider using the return-early pattern rather than the arrow antipattern

    def insert(self, value: T) -> None:
        """Insert an element into the BST."""
        if not self.value:
            self.value = value

        if self.value == value:  # Value exists.
            return

        if value < self.value:
            if self.lchild:
                return self.lchild.insert(value)
            
            self.lchild = BST(value)

        else:
            if self.rchild:
                return self.rchild.insert(value)
            
            self.rchild = BST(value)

Use comments sparingly

As you can see above, you can reduce your comments to hints about why the code does certain things. What the code does is described by the code itself already.

Usability

Your search() method currently only prints whether a match has been found. It should instead return the found element or raise an exception otherwise.

from __future__ import annotations

...

class NotFound(Exception):
    """Indicates that the requested element has not been found."""

...

    def search(self, value: T) -> BST:
        """Return the BST element with the requested value.
        Raise NotFound iff such an element does not exist within the BST.
        """
        if value == self.value:
            return self
        
        if value < self.value:
            if self.lchild:
                return self.lchild.search(value)

            raise NotFound()
        
        if self.rchild:
            return self.rchild.search(value)
        
        raise NotFound()