# Binary Search Tree – My own version of delete function

Posted on

Problem

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:

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

else:

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:

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:
``````

Solution

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
``````

## 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)
``````

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()
``````