Binary Tree

py_ds.datastructures.trees.base.BinaryTree

BinaryTree(items: Iterable[T] | None = None)

Bases: ABC, Generic[T]

Initialize a binary tree.

Parameters:

Name	Type	Description	Default
items	Iterable[T] | None	Optional iterable of items to insert into the tree. If None, an empty tree is created.	None

Source code in src/py_ds/datastructures/trees/base.py

def __init__(self, items: Iterable[T] | None = None):
    """Initialize a binary tree.

    Args:
        items: Optional iterable of items to insert into the tree. If None,
            an empty tree is created.
    """
    self._root: _BinaryNode[T] | None = None
    self.size: int = 0
    items = items or []
    for item in items:
        self.insert(item)

Attributes

is_empty property

is_empty: bool

Check if the tree is empty.

Returns:

Type	Description
bool	True if the tree contains no elements, False otherwise.

height property

height: int

Get the height of the tree.

Returns:

Type	Description
int	The height of the tree. Returns -1 for an empty tree, 0 for a tree
int	with only a root node, and increases by 1 for each level below.

Functions

insert abstractmethod

insert(value: T) -> None

Add a value to the tree.

Parameters:

Name	Type	Description	Default
value	T	The value to insert into the tree.	required

Source code in src/py_ds/datastructures/trees/base.py

@abstractmethod
def insert(self, value: T) -> None:
    """Add a value to the tree.

    Args:
        value: The value to insert into the tree.
    """

remove abstractmethod

remove(value: T) -> None

Remove a value from the tree.

Parameters:

Name	Type	Description	Default
value	T	The value to remove from the tree.	required

Source code in src/py_ds/datastructures/trees/base.py

@abstractmethod
def remove(self, value: T) -> None:
    """Remove a value from the tree.

    Args:
        value: The value to remove from the tree.
    """

clear

clear() -> None

Remove all elements from the tree.

Source code in src/py_ds/datastructures/trees/base.py

def clear(self) -> None:
    """Remove all elements from the tree."""
    self._root = None
    self.size = 0

__len__

__len__() -> int

Return the number of elements in the tree.

Returns:

Type	Description
int	The number of elements in the tree.

Source code in src/py_ds/datastructures/trees/base.py

def __len__(self) -> int:
    """Return the number of elements in the tree.

    Returns:
        The number of elements in the tree.
    """
    return self.size

inorder

inorder() -> Iterator[T]

Traverse the tree in inorder (left, root, right).

Yields:

Type	Description
T	Values from the tree in inorder traversal order.

Source code in src/py_ds/datastructures/trees/base.py

def inorder(self) -> Iterator[T]:
    """Traverse the tree in inorder (left, root, right).

    Yields:
        Values from the tree in inorder traversal order.
    """

    def _inorder(node: _BinaryNode[T] | None):
        if node is None:
            return
        yield from _inorder(node.left)
        yield node.value
        yield from _inorder(node.right)

    yield from _inorder(self._root)

preorder

preorder() -> Iterator[T]

Traverse the tree in preorder (root, left, right).

Yields:

Type	Description
T	Values from the tree in preorder traversal order.

Source code in src/py_ds/datastructures/trees/base.py

def preorder(self) -> Iterator[T]:
    """Traverse the tree in preorder (root, left, right).

    Yields:
        Values from the tree in preorder traversal order.
    """

    def _preorder(node: _BinaryNode[T] | None):
        if node is None:
            return
        yield node.value
        yield from _preorder(node.left)
        yield from _preorder(node.right)

    yield from _preorder(self._root)

postorder

postorder() -> Iterator[T]

Traverse the tree in postorder (left, right, root).

Yields:

Type	Description
T	Values from the tree in postorder traversal order.

Source code in src/py_ds/datastructures/trees/base.py

def postorder(self) -> Iterator[T]:
    """Traverse the tree in postorder (left, right, root).

    Yields:
        Values from the tree in postorder traversal order.
    """

    def _postorder(node: _BinaryNode[T] | None):
        if node is None:
            return
        yield from _postorder(node.left)
        yield from _postorder(node.right)
        yield node.value

    yield from _postorder(self._root)

level_order

level_order() -> Iterator[T]

Traverse the tree in level-order (breadth-first).

Yields:

Type	Description
T	Values from the tree in level-order traversal, from top to bottom
T	and left to right at each level.

Source code in src/py_ds/datastructures/trees/base.py

def level_order(self) -> Iterator[T]:
    """Traverse the tree in level-order (breadth-first).

    Yields:
        Values from the tree in level-order traversal, from top to bottom
        and left to right at each level.
    """
    visited = [self._root] if self._root else []
    while visited:
        node = visited.pop(0)
        yield node.value
        if node.left:
            visited.append(node.left)
        if node.right:
            visited.append(node.right)

__str__

__str__() -> str

Return a string representation of the tree.

Returns:

Type	Description
str	A visual string representation of the tree structure. Returns 'EMPTY'
str	if the tree is empty.

Source code in src/py_ds/datastructures/trees/base.py

def __str__(self) -> str:
    """Return a string representation of the tree.

    Returns:
        A visual string representation of the tree structure. Returns 'EMPTY'
        if the tree is empty.
    """
    if self._root is None:
        return 'EMPTY'

    def build_tree_str(node: _BinaryNode[T], prefix: str, is_left: bool) -> str:
        tree = ''

        if node.right:
            tree += build_tree_str(node.right, prefix + ('│   ' if is_left else '    '), False)

        tree += prefix + ('└── ' if is_left else '┌── ') + str(node.value) + '\n'

        if node.left:
            tree += build_tree_str(node.left, prefix + ('    ' if is_left else '│   '), True)
        return tree

    result = ''
    if self._root.right:
        right_result = build_tree_str(self._root.right, '', False)
        result += right_result

    result += f'{self._root.value}\n'

    if self._root.left:
        left_result = build_tree_str(self._root.left, '', True)
        result += left_result

    return result