data_structures.binary_tree.binary_search_tree ============================================== .. py:module:: data_structures.binary_tree.binary_search_tree .. autoapi-nested-parse:: 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) # doctest: +ELLIPSIS 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 ------- .. autoapisummary:: data_structures.binary_tree.binary_search_tree.BinarySearchTree data_structures.binary_tree.binary_search_tree.Node Functions --------- .. autoapisummary:: data_structures.binary_tree.binary_search_tree.inorder data_structures.binary_tree.binary_search_tree.postorder Module Contents --------------- .. py:class:: BinarySearchTree .. py:method:: __bool__() -> bool .. py:method:: __insert(value) -> None Insert a new node in Binary Search Tree with value label .. py:method:: __iter__() -> collections.abc.Iterator[int] .. py:method:: __reassign_nodes(node: Node, new_children: Node | None) -> None .. py:method:: __str__() -> str Return a string of all the Nodes using in order traversal .. py:method:: 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 .. py:method:: find_kth_smallest(k: int, node: Node) -> int Return the kth smallest element in a binary search tree .. py:method:: 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)} .. py:method:: 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)})} .. py:method:: inorder(arr: list, node: Node | None) -> None Perform an inorder traversal and append values of the nodes to a list named arr .. py:method:: insert(*values) -> Self .. py:method:: preorder_traverse(node: Node | None) -> collections.abc.Iterable .. py:method:: remove(value: int) -> None .. py:method:: 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. .. py:method:: 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 .. py:attribute:: root :type: Node | None :value: None .. py:class:: Node .. py:method:: __iter__() -> collections.abc.Iterator[int] >>> list(Node(0)) [0] >>> list(Node(0, Node(-1), Node(1), None)) [-1, 0, 1] .. py:method:: __repr__() -> str .. py:property:: is_right :type: bool .. py:attribute:: left :type: Node | None :value: None .. py:attribute:: parent :type: Node | None :value: None .. py:attribute:: right :type: Node | None :value: None .. py:attribute:: value :type: int .. py:function:: inorder(curr_node: Node | None) -> list[Node] inorder (left, self, right) .. py:function:: postorder(curr_node: Node | None) -> list[Node] postOrder (left, right, self)