Skip to main content
added 49 characters in body
Source Link
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           if self.lchild:
                return self.lchild.search(value)

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

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