Binary Search Tree

Interface

The implementation of the binary search tree (BST).

class TreeNode(data: int)

The atomic elements of the binary tree implemented with linked list.

__init__(data: int) → None

Initianlize a tree node.

Variables:

• data – The data of the node.

• left – The pointer to the left node.

• right – The pointer to the right node.

class BST

Binary Search Tree impletemented with linked list.

__init__()

Initianlize an empty binary search tree.

Variables:

head – The pointer to the root node of the binary search tree.

find(element: int) → TreeNode

Non-recursion version of the find operation in binary search tree.

Parameters:

element – The element to find.

Returns:

The target node.

find_min() → TreeNode

Find the minimum element in the bst.

Returns:

The minimum node.

find_max() → TreeNode

Find the maximum element in the bst.

Returns:

The maximum node

insert(element: int, bst: Sentinel | TreeNode = Sentinel) → None

Insert the element into the bst and ensure it remains a bst.

Parameters:

• element – The element to insert.

• bst – The bst to be inserted. Optional, defaults to self.head if not proviede.

delete(element: int, bst: Sentinel | TreeNode = Sentinel) → TreeNode | None

Delete the element from the bst.

Parameters:

• element – The element to be deleted.

• bst – The bst to be delteted. Optional, defaults to self.head if not proviede.

Returns:

The new root node of the tree bst.