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 and self.lchild:
return self.lchild.search(value)
if self.rchild:
return self.rchild.search(value)
raise NotFound()