binary_search_tree.py

r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)
r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)
r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)
r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)
r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)
r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)
r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)
r"""
A binary search Tree

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

>>> t = BinarySearchTree()
>>> t.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)

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
"""
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass
fromtypingimportAny


@dataclass
classNode:
value: int
left: Node|None=None
right: Node|None=None
parent: Node|None=None# Added in order to delete a node easier

def__iter__(self) ->Iterator[int]:
"""
 >>> list(Node(0))
 [0]
 >>> list(Node(0, Node(-1), Node(1), None))
 [-1, 0, 1]
 """
yieldfromself.leftor []
yieldself.value
yieldfromself.rightor []

def__repr__(self) ->str:
frompprintimportpformat

ifself.leftisNoneandself.rightisNone:
returnstr(self.value)
returnpformat({f"{self.value}": (self.left, self.right)}, indent=1)

@property
defis_right(self) ->bool:
returnbool(self.parentandselfisself.parent.right)


@dataclass
classBinarySearchTree:
root: Node|None=None

def__bool__(self) ->bool:
returnbool(self.root)

def__iter__(self) ->Iterator[int]:
yieldfromself.rootor []

def__str__(self) ->str:
"""
 Return a string of all the Nodes using in order traversal
 """
returnstr(self.root)

def__reassign_nodes(self, node: Node, new_children: Node|None) ->None:
ifnew_childrenisnotNone: # reset its kids
new_children.parent=node.parent
ifnode.parentisnotNone: # reset its parent
ifnode.is_right: # If it is the right child
node.parent.right=new_children
else:
node.parent.left=new_children
else:
self.root=new_children

defempty(self) ->bool:
returnself.rootisNone

def__insert(self, value) ->None:
"""
 Insert a new node in Binary Search Tree with value label
 """
new_node=Node(value) # create a new Node
ifself.empty(): # if Tree is empty
self.root=new_node# set its root
else: # Tree is not empty
parent_node=self.root# from root
ifparent_nodeisNone:
return
whileTrue: # While we don't get to a leaf
ifvalue<parent_node.value: # We go left
ifparent_node.leftisNone:
parent_node.left=new_node# We insert the new node in a leaf
break
else:
parent_node=parent_node.left
else:
ifparent_node.rightisNone:
parent_node.right=new_node
break
else:
parent_node=parent_node.right
new_node.parent=parent_node

definsert(self, *values) ->None:
forvalueinvalues:
self.__insert(value)

defsearch(self, value) ->Node|None:
ifself.empty():
raiseIndexError("Warning: Tree is empty! please use another.")
else:
node=self.root
# use lazy evaluation here to avoid NoneType Attribute error
whilenodeisnotNoneandnode.valueisnotvalue:
node=node.leftifvalue<node.valueelsenode.right
returnnode

defget_max(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the right branch
 """
ifnodeisNone:
ifself.rootisNone:
returnNone
node=self.root

ifnotself.empty():
whilenode.rightisnotNone:
node=node.right
returnnode

defget_min(self, node: Node|None=None) ->Node|None:
"""
 We go deep on the left branch
 """
ifnodeisNone:
node=self.root
ifself.rootisNone:
returnNone
ifnotself.empty():
node=self.root
whilenode.leftisnotNone:
node=node.left
returnnode

defremove(self, value: int) ->None:
# Look for the node with that label
node=self.search(value)
ifnodeisNone:
msg=f"Value {value} not found"
raiseValueError(msg)

ifnode.leftisNoneandnode.rightisNone: # If it has no children
self.__reassign_nodes(node, None)
elifnode.leftisNone: # Has only right children
self.__reassign_nodes(node, node.right)
elifnode.rightisNone: # Has only left children
self.__reassign_nodes(node, node.left)
else:
predecessor=self.get_max(
node.left
 ) # Gets the max value of the left branch
self.remove(predecessor.value) # type: ignore
node.value= (
predecessor.value# type: ignore
 ) # Assigns the value to the node to delete and keep tree structure

defpreorder_traverse(self, node: Node|None) ->Iterable:
ifnodeisnotNone:
yieldnode# Preorder Traversal
yieldfromself.preorder_traverse(node.left)
yieldfromself.preorder_traverse(node.right)

deftraversal_tree(self, traversal_function=None) ->Any:
"""
 This function traversal the tree.
 You can pass a function to traversal the tree as needed by client code
 """
iftraversal_functionisNone:
returnself.preorder_traverse(self.root)
else:
returntraversal_function(self.root)

definorder(self, arr: list, node: Node|None) ->None:
"""Perform an inorder traversal and append values of the nodes to
 a list named arr"""
ifnode:
self.inorder(arr, node.left)
arr.append(node.value)
self.inorder(arr, node.right)

deffind_kth_smallest(self, k: int, node: Node) ->int:
"""Return the kth smallest element in a binary search tree"""
arr: list[int] = []
self.inorder(arr, node) # append all values to list using inorder traversal
returnarr[k-1]


definorder(curr_node: Node|None) ->list[Node]:
"""
 inorder (left, self, right)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=inorder(curr_node.left) + [curr_node] +inorder(curr_node.right)
returnnode_list


defpostorder(curr_node: Node|None) ->list[Node]:
"""
 postOrder (left, right, self)
 """
node_list= []
ifcurr_nodeisnotNone:
node_list=postorder(curr_node.left) +postorder(curr_node.right) + [curr_node]
returnnode_list


if__name__=="__main__":
importdoctest

doctest.testmod(verbose=True)