data_structures.binary_tree.binary_search_tree_recursive

This is a python3 implementation of binary search tree using recursion

To run tests: python -m unittest binary_search_tree_recursive.py

To run an example: python binary_search_tree_recursive.py

Classes

BinarySearchTree

BinarySearchTreeTest

A class whose instances are single test cases.

Node

Functions

binary_search_tree_example(→ None)

Example

Module Contents

class data_structures.binary_tree.binary_search_tree_recursive.BinarySearchTree
_get_lowest_node(node: Node) → Node
_inorder_traversal(node: Node | None) → collections.abc.Iterator[Node]
_preorder_traversal(node: Node | None) → collections.abc.Iterator[Node]
_put(node: Node | None, label: int, parent: Node | None = None) → Node
_reassign_nodes(node: Node, new_children: Node | None) → None
empty() → None

Empties the tree

>>> t = BinarySearchTree()
>>> assert t.root is None
>>> t.put(8)
>>> assert t.root is not None
exists(label: int) → bool

Checks if a node exists in the tree

>>> t = BinarySearchTree()
>>> t.put(8)
>>> t.put(10)
>>> t.exists(8)
True

>>> t.exists(3)
False
get_max_label() → int

Gets the max label inserted in the tree

>>> t = BinarySearchTree()
>>> t.get_max_label()
Traceback (most recent call last):
    ...
ValueError: Binary search tree is empty

>>> t.put(8)
>>> t.put(10)
>>> t.get_max_label()
10
get_min_label() → int

Gets the min label inserted in the tree

>>> t = BinarySearchTree()
>>> t.get_min_label()
Traceback (most recent call last):
    ...
ValueError: Binary search tree is empty

>>> t.put(8)
>>> t.put(10)
>>> t.get_min_label()
8
inorder_traversal() → collections.abc.Iterator[Node]

Return the inorder traversal of the tree

>>> t = BinarySearchTree()
>>> [i.label for i in t.inorder_traversal()]
[]

>>> t.put(8)
>>> t.put(10)
>>> t.put(9)
>>> [i.label for i in t.inorder_traversal()]
[8, 9, 10]
is_empty() → bool

Checks if the tree is empty

>>> t = BinarySearchTree()
>>> t.is_empty()
True
>>> t.put(8)
>>> t.is_empty()
False
preorder_traversal() → collections.abc.Iterator[Node]

Return the preorder traversal of the tree

>>> t = BinarySearchTree()
>>> [i.label for i in t.preorder_traversal()]
[]

>>> t.put(8)
>>> t.put(10)
>>> t.put(9)
>>> [i.label for i in t.preorder_traversal()]
[8, 10, 9]
put(label: int) → None

Put a new node in the tree

>>> t = BinarySearchTree()
>>> t.put(8)
>>> assert t.root.parent is None
>>> assert t.root.label == 8

>>> t.put(10)
>>> assert t.root.right.parent == t.root
>>> assert t.root.right.label == 10

>>> t.put(3)
>>> assert t.root.left.parent == t.root
>>> assert t.root.left.label == 3
remove(label: int) → None

Removes a node in the tree

>>> t = BinarySearchTree()
>>> t.put(8)
>>> t.put(10)
>>> t.remove(8)
>>> assert t.root.label == 10

>>> t.remove(3)
Traceback (most recent call last):
    ...
ValueError: Node with label 3 does not exist
search(label: int) → Node

Searches a node in the tree

>>> t = BinarySearchTree()
>>> t.put(8)
>>> t.put(10)
>>> node = t.search(8)
>>> assert node.label == 8

>>> node = t.search(3)
Traceback (most recent call last):
    ...
ValueError: Node with label 3 does not exist
root: Node | None = None
class data_structures.binary_tree.binary_search_tree_recursive.BinarySearchTreeTest(methodName='runTest')

Bases: unittest.TestCase

A class whose instances are single test cases.

By default, the test code itself should be placed in a method named ‘runTest’.

If the fixture may be used for many test cases, create as many test methods as are needed. When instantiating such a TestCase subclass, specify in the constructor arguments the name of the test method that the instance is to execute.

Test authors should subclass TestCase for their own tests. Construction and deconstruction of the test’s environment (‘fixture’) can be implemented by overriding the ‘setUp’ and ‘tearDown’ methods respectively.

If it is necessary to override the __init__ method, the base class __init__ method must always be called. It is important that subclasses should not change the signature of their __init__ method, since instances of the classes are instantiated automatically by parts of the framework in order to be run.

When subclassing TestCase, you can set these attributes: * failureException: determines which exception will be raised when

the instance’s assertion methods fail; test methods raising this exception will be deemed to have ‘failed’ rather than ‘errored’.

  • longMessage: determines whether long messages (including repr of

    objects used in assert methods) will be printed on failure in addition to any explicit message passed.

  • maxDiff: sets the maximum length of a diff in failure messages

    by assert methods using difflib. It is looked up as an instance attribute so can be configured by individual tests if required.

static _get_binary_search_tree() → BinarySearchTree

8

/

3 10

/

1 6 14

/ /

4 7 13

5

test_empty() → None
test_exists() → None
test_get_max_label() → None
test_get_min_label() → None
test_inorder_traversal() → None
test_is_empty() → None
test_preorder_traversal() → None
test_put() → None
test_remove() → None
test_remove_2() → None
class data_structures.binary_tree.binary_search_tree_recursive.Node(label: int, parent: Node | None)
label
left: Node | None = None
parent
right: Node | None = None
data_structures.binary_tree.binary_search_tree_recursive.binary_search_tree_example() → None
Example

8

/

3 10

/

1 6 14

/ /

4 7 13 5

Example After Deletion

4

/

1 7

5