binary_search_tree

binary_search_tree#

Classes#

BinarySearchTree

A class representing a Binary Search Tree (BST).

Module Contents#

class binary_search_tree.BinarySearchTree#

A class representing a Binary Search Tree (BST).

insert(key)#

Inserts a key into the BST while maintaining the BST properties.

search(key, algorithm='dfs')#

Searches for a key in the BST using the specified search algorithm (‘dfs’ or ‘bfs’).

delete(key)#

Deletes a key from the BST while preserving the BST structure.

list_to_tree(elements)#

Constructs a BST from a list of integers.

root = None#
insert(key)#

Inserts a key into the Binary Search Tree (BST) while maintaining its properties.

  • Values smaller than the current node’s key go to the left subtree.

  • Values larger than the current node’s key go to the right subtree.

  • Duplicate values are not allowed.

Parameters:

key (int) – The value to insert into the BST.

Raises:

TypeError – If the key is not an integer or is None.

Examples

>>> bst = BinarySearchTree()
>>> bst.insert(10)
>>> bst.insert(5)
>>> bst.insert(15)
>>> bst.root.left.key
5
>>> bst.root.right.key
15
search(key)#

Searches for a key in the Binary Search Tree (BST).

Parameters:

key (int) – The value to search for in the BST.

Returns:

  • The Node object containing the specified key if found.

  • None if the key does not exist or the tree is empty.

Return type:

Node or None

Raises:

TypeError – If the key is not an integer or is None.

Examples

>>> bst = BinarySearchTree()
>>> bst.insert(10)
>>> bst.insert(5)
>>> bst.insert(15)
>>> bst.search(5).key
5
>>> bst.search(20) is None
True
delete(key)#

Deletes a key from the Binary Search Tree (BST) while preserving its structure.

  • If the node has no children, it is simply removed.

  • If the node has one child, it is replaced by its child.

  • If the node has two children, it is replaced by the in-order successor (smallest node in the right subtree).

Parameters:

key (int) – The value to delete from the BST.

Returns:

  • True if the key was found and deleted.

  • False if the key was not found.

Return type:

bool

Raises:

TypeError – If the key is not an integer or is None.

Examples

>>> bst = BinarySearchTree()
>>> bst.insert(10)
>>> bst.insert(5)
>>> bst.insert(15)
>>> bst.delete(10)
True
>>> bst.delete(20)
False
static list_to_tree(elements)#

Constructs a Binary Search Tree (BST) from a list of integers.

Parameters:

elements (list of int) – A list of integers to be inserted into the BST.

Returns:

A BinarySearchTree object containing all elements from the input list.

Return type:

BinarySearchTree

Raises:

ValueError – If the input is not a list or contains non-integer elements.

Examples

>>> elements = [10, 5, 15, 12, 20]
>>> bst = BinarySearchTree.list_to_tree(elements)
>>> bst.root.key
10
>>> bst.root.left.key
5
>>> bst.root.right.key
15