data_structures.binary_tree.binary_search_tree

A binary search Tree

Example

8

/

3 10

/

1 6 14

/ /

4 7 13

>>> t = BinarySearchTree().insert(8, 3, 6, 1, 10, 14, 13, 4, 7)
>>> print(" ".join(repr(i.value) for i in t.traversal_tree()))
8 3 1 6 4 7 10 14 13

>>> tuple(i.value for i in t.traversal_tree(inorder))
(1, 3, 4, 6, 7, 8, 10, 13, 14)
>>> tuple(t)
(1, 3, 4, 6, 7, 8, 10, 13, 14)
>>> t.find_kth_smallest(3, t.root)
4
>>> tuple(t)[3-1]
4

>>> print(" ".join(repr(i.value) for i in t.traversal_tree(postorder)))
1 4 7 6 3 13 14 10 8
>>> t.remove(20)
Traceback (most recent call last):
    ...
ValueError: Value 20 not found
>>> BinarySearchTree().search(6)
Traceback (most recent call last):
    ...
IndexError: Warning: Tree is empty! please use another.

Other example:

>>> testlist = (8, 3, 6, 1, 10, 14, 13, 4, 7)
>>> t = BinarySearchTree()
>>> for i in testlist:
...     t.insert(i)  
BinarySearchTree(root=8)
BinarySearchTree(root={'8': (3, None)})
BinarySearchTree(root={'8': ({'3': (None, 6)}, None)})
BinarySearchTree(root={'8': ({'3': (1, 6)}, None)})
BinarySearchTree(root={'8': ({'3': (1, 6)}, 10)})
BinarySearchTree(root={'8': ({'3': (1, 6)}, {'10': (None, 14)})})
BinarySearchTree(root={'8': ({'3': (1, 6)}, {'10': (None, {'14': (13, None)})})})
BinarySearchTree(root={'8': ({'3': (1, {'6': (4, None)})}, {'10': (None, {'14': ...
BinarySearchTree(root={'8': ({'3': (1, {'6': (4, 7)})}, {'10': (None, {'14': (13, ...

Prints all the elements of the list in order traversal >>> print(t) {‘8’: ({‘3’: (1, {‘6’: (4, 7)})}, {‘10’: (None, {‘14’: (13, None)})})}

Test existence >>> t.search(6) is not None True >>> 6 in t True >>> t.search(-1) is not None False >>> -1 in t False

>>> t.search(6).is_right
True
>>> t.search(1).is_right
False

>>> t.get_max().value
14
>>> max(t)
14
>>> t.get_min().value
1
>>> min(t)
1
>>> t.empty()
False
>>> not t
False
>>> for i in testlist:
...     t.remove(i)
>>> t.empty()
True
>>> not t
True

Classes

BinarySearchTree
Node

Functions

inorder(→ list[Node])	inorder (left, self, right)
postorder(→ list[Node])	postOrder (left, right, self)

Module Contents

class data_structures.binary_tree.binary_search_tree.BinarySearchTree

__bool__() → bool

__insert(value) → None

Insert a new node in Binary Search Tree with value label

__iter__() → collections.abc.Iterator[int]

__reassign_nodes(node: Node, new_children: Node | None) → None

__str__() → str

Return a string of all the Nodes using in order traversal

empty() → bool

Returns True if the tree does not have any element(s). False if the tree has element(s).

>>> BinarySearchTree().empty()
True
>>> BinarySearchTree().insert(1).empty()
False
>>> BinarySearchTree().insert(8, 3, 6, 1, 10, 14, 13, 4, 7).empty()
False

find_kth_smallest(k: int, node: Node) → int

Return the kth smallest element in a binary search tree

get_max(node: Node | None = None) → Node | None

We go deep on the right branch

>>> BinarySearchTree().insert(10, 20, 30, 40, 50).get_max()
50
>>> BinarySearchTree().insert(-5, -1, 0.1, -0.3, -4.5).get_max()
{'0.1': (-0.3, None)}
>>> BinarySearchTree().insert(1, 78.3, 30, 74.0, 1).get_max()
{'78.3': ({'30': (1, 74.0)}, None)}
>>> BinarySearchTree().insert(1, 783, 30, 740, 1).get_max()
{'783': ({'30': (1, 740)}, None)}

get_min(node: Node | None = None) → Node | None

We go deep on the left branch

>>> BinarySearchTree().insert(10, 20, 30, 40, 50).get_min()
{'10': (None, {'20': (None, {'30': (None, {'40': (None, 50)})})})}
>>> BinarySearchTree().insert(-5, -1, 0, -0.3, -4.5).get_min()
{'-5': (None, {'-1': (-4.5, {'0': (-0.3, None)})})}
>>> BinarySearchTree().insert(1, 78.3, 30, 74.0, 1).get_min()
{'1': (None, {'78.3': ({'30': (1, 74.0)}, None)})}
>>> BinarySearchTree().insert(1, 783, 30, 740, 1).get_min()
{'1': (None, {'783': ({'30': (1, 740)}, None)})}

inorder(arr: list, node: Node | None) → None

Perform an inorder traversal and append values of the nodes to a list named arr

insert(*values) → Self

preorder_traverse(node: Node | None) → collections.abc.Iterable

remove(value: int) → None

search(value) → Node | None

>>> tree = BinarySearchTree().insert(10, 20, 30, 40, 50)
>>> tree.search(10)
{'10': (None, {'20': (None, {'30': (None, {'40': (None, 50)})})})}
>>> tree.search(20)
{'20': (None, {'30': (None, {'40': (None, 50)})})}
>>> tree.search(30)
{'30': (None, {'40': (None, 50)})}
>>> tree.search(40)
{'40': (None, 50)}
>>> tree.search(50)
50
>>> tree.search(5) is None  # element not present
True
>>> tree.search(0) is None  # element not present
True
>>> tree.search(-5) is None  # element not present
True
>>> BinarySearchTree().search(10)
Traceback (most recent call last):
    ...
IndexError: Warning: Tree is empty! please use another.

traversal_tree(traversal_function=None) → Any

This function traversal the tree. You can pass a function to traversal the tree as needed by client code

root: Node | None = None

class data_structures.binary_tree.binary_search_tree.Node

__iter__() → collections.abc.Iterator[int]

>>> list(Node(0))
[0]
>>> list(Node(0, Node(-1), Node(1), None))
[-1, 0, 1]

__repr__() → str

property is_right: bool

left: Node | None = None

parent: Node | None = None

right: Node | None = None

value: int

data_structures.binary_tree.binary_search_tree.inorder(curr_node: Node | None) → list[Node]

inorder (left, self, right)

data_structures.binary_tree.binary_search_tree.postorder(curr_node: Node | None) → list[Node]

postOrder (left, right, self)