data_structures.binary_tree.binary_search_tree_recursive
========================================================

.. py:module:: data_structures.binary_tree.binary_search_tree_recursive

.. autoapi-nested-parse::

   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
-------

.. autoapisummary::

   data_structures.binary_tree.binary_search_tree_recursive.BinarySearchTree
   data_structures.binary_tree.binary_search_tree_recursive.BinarySearchTreeTest
   data_structures.binary_tree.binary_search_tree_recursive.Node


Functions
---------

.. autoapisummary::

   data_structures.binary_tree.binary_search_tree_recursive.binary_search_tree_example


Module Contents
---------------

.. py:class:: BinarySearchTree

   .. py:method:: _get_lowest_node(node: Node) -> Node


   .. py:method:: _inorder_traversal(node: Node | None) -> collections.abc.Iterator[Node]


   .. py:method:: _preorder_traversal(node: Node | None) -> collections.abc.Iterator[Node]


   .. py:method:: _put(node: Node | None, label: int, parent: Node | None = None) -> Node


   .. py:method:: _reassign_nodes(node: Node, new_children: Node | None) -> None


   .. py:method:: _search(node: Node | None, label: int) -> Node


   .. py:method:: empty() -> None

      Empties the tree

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



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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]



   .. py:method:: is_empty() -> bool

      Checks if the tree is empty

      >>> t = BinarySearchTree()
      >>> t.is_empty()
      True
      >>> t.put(8)
      >>> t.is_empty()
      False



   .. py:method:: 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]



   .. py:method:: 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



   .. py:method:: 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



   .. py:method:: 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



   .. py:attribute:: root
      :type:  Node | None
      :value: None



.. py:class:: BinarySearchTreeTest(methodName='runTest')

   Bases: :py:obj:`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.


   .. py:method:: _get_binary_search_tree() -> BinarySearchTree
      :staticmethod:


          8
         / \
        3   10
       / \    \
      1   6    14
         / \   /
        4   7 13
         \
          5



   .. py:method:: test_empty() -> None


   .. py:method:: test_exists() -> None


   .. py:method:: test_get_max_label() -> None


   .. py:method:: test_get_min_label() -> None


   .. py:method:: test_inorder_traversal() -> None


   .. py:method:: test_is_empty() -> None


   .. py:method:: test_preorder_traversal() -> None


   .. py:method:: test_put() -> None


   .. py:method:: test_remove() -> None


   .. py:method:: test_remove_2() -> None


   .. py:method:: test_search() -> None


.. py:class:: Node(label: int, parent: Node | None)

   .. py:attribute:: label


   .. py:attribute:: left
      :type:  Node | None
      :value: None



   .. py:attribute:: parent


   .. py:attribute:: right
      :type:  Node | None
      :value: None



.. py:function:: binary_search_tree_example() -> None

   Example
                 8
                / \
               3   10
              / \    \
             1   6    14
                / \   /
               4   7 13
               \
               5

   Example After Deletion
                 4
                / \
               1   7
                    \
                     5