Function bst

binarytree/__init__.py:2392–2465

Generate a random BST (binary search tree) and return its root node. :param height: Height of the BST (default: 3, range: 0 - 9 inclusive). :type height: int :param is_perfect: If set to True (default: False), a perfect BST with all levels filled is returned. If set to False, a

(
    height: int = 3,
    is_perfect: bool = False,
    letters: bool = False,
)

def bst(
    height: int = 3,
    is_perfect: bool = False,
    letters: bool = False,
) -> Optional[Node]:
    """Generate a random BST (binary search tree) and return its root node.

    :param height: Height of the BST (default: 3, range: 0 - 9 inclusive).
    :type height: int
    :param is_perfect: If set to True (default: False), a perfect BST with all
        levels filled is returned. If set to False, a perfect BST may still be
        generated by chance.
    :type is_perfect: bool
    :param letters: If set to True (default: False), uppercase alphabet letters are
        used for node values instead of numbers.
    :type letters: bool
    :return: Root node of the BST.
    :rtype: binarytree.Node
    :raise binarytree.exceptions.TreeHeightError: If height is invalid.

    **Example**:

    .. doctest::

        >>> from binarytree import bst
        >>>
        >>> root = bst()
        >>>
        >>> root.height
        3
        >>> root.is_bst
        True

    .. doctest::

        >>> from binarytree import bst
        >>>
        >>> root = bst(10)  # doctest: +IGNORE_EXCEPTION_DETAIL
        Traceback (most recent call last):
         ...
        binarytree.exceptions.TreeHeightError: height must be an int between 0 - 9
    """
    _validate_tree_height(height)
    if is_perfect:
        return _generate_perfect_bst(height)

    numbers = _generate_random_numbers(height)
    values: NodeValueList = (
        list(map(number_to_letters, numbers)) if letters else numbers
    )
    leaf_count = _generate_random_leaf_count(height)

    root_node = Node(values.pop(0))
    leaves = set()

    for value in values:
        node = root_node
        depth = 0