Binary Search Tree Implementation (practice)

Question

Note: I do know that Python libraries provide Binary Search Tree. This implementation has been done to practice python, and data structures and Algorithms.

This is a implemented Binary Search Tree, feel free to make any suggestions about syntax, logic, or simply anything that you think i should become aware of.

Methods:

tree_insert(i) - handles inserting values, it will refuse to accept a key that already exist.
walk_tree(type) - walks the tree from root, default is in-order
inorder_tree_walk(node)
preorder_tree_walk(node)
postorder_tree_walk(node)
Search_tree_from_root(search_type, key) - looks for key from root based on type given
tree_min() - finds max key
tree_max() - finds min key
tree_search_recursive(key) - search for key from root recursively
tree_search_iterative(key) - search for key from root iteratively
tree_successor(key)- finds successor of the key
tree_predecessor(key)- finds predecessor of the key
tree_delete(i) - handles deleting a key. Delete method, uses the transplant method to move branches around
transplant(second,first)
tree_burn() - deletes everything in tree

How to use:

from binarySearchTree import BTree
def main():
print("_____INSERT____")
my_tree = BTree()
my_list = [12, 5, 18, 2, 9, 15, 19, 17, 13]
for i in my_list:
 my_tree.tree_insert(i)
print("INSERT DONE")
print("______________TREE_INSET_TRY_Duplicate______________________")
my_tree.tree_insert(12)
print("____________GET_ROOT_KEY_____________________")
print(my_tree.get_root())
print("______________TREE_WALK______________________")
my_tree.walk_tree(3)
my_tree.walk_tree(2)
my_tree.walk_tree()
print("__________TREE_SEARCH_FROM_ROOT_______________")
my_tree.search_tree_from_root(0, 15)
my_tree.search_tree_from_root(1, 19)
my_tree.search_tree_from_root(2)
my_tree.search_tree_from_root(3)
print("_____KEY_SUCCESSOR____")
my_tree.tree_successor(12)
print("_____KEY_PREDECESSOR____")
my_tree.tree_predecessor(5)
print("______________TREE_Delete______________________")
my_tree.tree_delete(100)
print("______________TREE_Delete______________________")
my_tree.tree_delete(15)
print("______________TREE_WALK______________________")
my_tree.walk_tree()
print("______________TREE_BURN______________________")
my_tree.burn_tree()
if __name__ == "__main__":
 main()

OutPUT:

_____INSERT____
INSERT DONE
______________TREE_INSET_TRY_Duplicate______________________
12 already Exist, can not add
____________GET_ROOT_KEY_____________________
12
______________TREE_WALK______________________
_____TREE_WALK_POSTORDER____
2
9
5
13
17
15
19
18
12
_____TREE_WALK_PREORDER____
12
5
2
9
18
15
13
17
19
_____TREE_WALK_INORDER____
2
5
9
12
13
15
17
18
19
__________TREE_SEARCH_FROM_ROOT_______________
_____ITERATIVE_TREE_SEARCH____
15
_____RECURSIVE_TREE_SEARCH____
19
_____TREE_MAX____
19
_____TREE_MIN____
2
_____KEY_SUCCESSOR____
13
_____KEY_PREDECESSOR____
2
______________TREE_Delete______________________
search Done
Not Found
______________TREE_Delete______________________
search Done
Delete Done
______________TREE_WALK______________________
_____TREE_WALK_INORDER____
2
5
9
12
13
17
18
19
______________TREE_BURN______________________
19
search Done
Delete Done
18
search Done
Delete Done
17
search Done
Delete Done
13
search Done
Delete Done
12
search Done
Delete Done
9
search Done
Delete Done
5
search Done
Delete Done
2
search Done
Delete Done
Process finished with exit code 0

Classes:

# simple node class
class TreeNode:
 # constructor
 def __init__(self, data=None):
 self.value = data
 self.right_child = None
 self.left_child = None
 # only used in delete and transplant can also use predecessor and SUCCESSOR instead
 self.prev_node = None
# binary search tree class
class BTree:
 # constructor
 def __init__(self):
 self.root = TreeNode(None)
 self.count = 0
 # insert method
 def tree_insert(self, value):
 # make new node
 new_node = TreeNode(value)
 # pointer that walks the tree to find the spot
 tracer = self.root
 # follow the pointer that is walking the tree to find a spot, always one step behind
 tracer_trailer = None
 while tracer is not None:
 tracer_trailer = tracer
 if tracer.value is None:
 break
 else:
 if new_node.value < tracer.value:
 tracer = tracer.left_child
 elif new_node.value == tracer.value:
 print(value, " already Exist, can not add")
 break
 else:
 tracer = tracer.right_child
 self.count += 1
 # Set Pointers that cause key to be inserted
 if tracer_trailer.value is None:
 self.root = new_node
 elif new_node.value == tracer_trailer.value:
 return False
 elif new_node.value < tracer_trailer.value:
 new_node.prev_node = tracer_trailer
 tracer_trailer.left_child = new_node
 else:
 new_node.prev_node = tracer_trailer
 tracer_trailer.right_child = new_node
# delete method, uses the transplant method to move branches around
 def tree_delete(self, key):
 root = self.root
 if root is not None:
 node = self.tree_search_iterative(root, key)
 print("search Done")
 if node is not None:
 # removing node has no left child
 if node.left_child is None:
 self.transplant(node, node.right_child)
 # removing node has no right child
 elif node.right_child is None:
 self.transplant(node, node.left_child)
 # removing node has two children
 else:
 # find successor in that side
 temp = self.tree_min(node.right_child)
 if temp.prev_node != node:
 self.transplant(temp, temp.right_child)
 temp.right_child = node.right_child
 temp.right_child.prev_node = temp
 self.transplant(node, temp)
 temp.left_child = node.left_child
 temp.left_child.prev_node = temp
 print("Delete Done")
 self.count -= 1
 else:
 print("Not Found")
 # used in delete; handles moving nodes and transplanting nodes
 def transplant(self, first_node, second_node):
 if first_node.prev_node is None:
 self.root = second_node
 elif first_node == first_node.prev_node.left_child:
 first_node.prev_node.left_child = second_node
 else:
 first_node.prev_node.right_child = second_node
 if second_node is not None:
 second_node.prev_node = first_node.prev_node
# --------in-order, pre-order, post-order tree walks-------------
 def inorder_tree_walk(self, node):
 if node is not None:
 self.inorder_tree_walk(node.left_child)
 print(node.value)
 self.inorder_tree_walk(node.right_child)
 def preorder_tree_walk(self, node):
 if node is not None:
 print(node.value)
 self.preorder_tree_walk(node.left_child)
 self.preorder_tree_walk(node.right_child)
 def postorder_tree_walk(self, node):
 if node is not None:
 self.postorder_tree_walk(node.left_child)
 self.postorder_tree_walk(node.right_child)
 print(node.value)
 # accessor to three different tree walks, will do it from root, default is in-order
 def walk_tree(self, walk_type=None):
 root = self.root
 if walk_type == 3:
 print("_____TREE_WALK_POSTORDER____")
 self.postorder_tree_walk(root)
 elif walk_type == 2:
 print("_____TREE_WALK_PREORDER____")
 self.preorder_tree_walk(root)
 else:
 print("_____TREE_WALK_INORDER____")
 self.inorder_tree_walk(root)
# --------recursive, iterative, max, min, search methods-------------
 def tree_search_recursive(self, node, key):
 if node is not None:
 if node is not None:
 if key == node.value:
 return key
 if key < node.value:
 return self.tree_search_recursive(node.left_child, key)
 else:
 return self.tree_search_recursive(node.right_child, key)
 else:
 print("NOT FOUND")
 def tree_search_iterative(self, node, key):
 if key is not None:
 while True:
 if node is None:
 return None
 if key == node.value:
 break
 if key < node.value:
 node = node.left_child
 else:
 node = node.right_child
 return node
 else:
 print("NOT FOUND")
 def tree_max(self, node):
 if node is not None:
 while node.right_child is not None:
 node = node.right_child
 return node
 else:
 print("Tree is empty")
 def tree_min(self, node):
 if node is not None:
 while node.left_child is not None:
 node = node.left_child
 return node
 else:
 print("Tree is empty")
 # search for a key using iterative, recursive, or search for max and min from root, default is Iterative
 def search_tree_from_root(self, search_type=None, key=None):
 root = self.root
 if root is not None:
 if search_type == 3:
 print("_____TREE_MIN____")
 found_node = self.tree_min(root)
 if found_node is not None:
 print(found_node.value)
 else:
 print("Not Found")
 elif search_type == 2:
 print("_____TREE_MAX____")
 found_node = self.tree_max(root)
 if found_node is not None:
 print(found_node.value)
 else:
 print("Not Found")
 elif search_type == 1:
 print("_____RECURSIVE_TREE_SEARCH____")
 found_node = self.tree_search_recursive(root, key)
 if found_node is not None:
 print(found_node)
 else:
 print("Not Found")
 elif search_type == 0:
 print("_____ITERATIVE_TREE_SEARCH____")
 found_node = self.tree_search_iterative(root, key)
 if found_node is not None:
 print(found_node.value)
 else:
 print("Not Found")
 else:
 print("Tree is Empty")
# successor and predecessor methods
 def tree_successor(self, key):
 root = self.root
 if root is not None:
 node = self.tree_search_iterative(root, key)
 if node.right_child is not None:
 found_node = self.tree_min(node.right_child)
 if found_node is not None:
 print(found_node.value)
 return found_node
 prev = node.prev_node
 while prev is not None and node == node.right_child:
 node = prev
 prev = prev.prev_node
 if prev is not None:
 print(prev.value)
 return prev
 else:
 print("Tree is empty")
 def tree_predecessor(self, key):
 root = self.root
 if root is not None:
 node = self.tree_search_iterative(root, key)
 if node.left_child is not None:
 found_node = self.tree_max(node.left_child)
 if found_node is not None:
 print(found_node.value)
 return found_node
 prev = node.prev_node
 while prev is not None and node == node.left_child:
 node = prev
 prev = prev.prev_node
 if prev is not None:
 print(prev.value)
 return prev
 else:
 print("Tree is empty")
 def get_root(self):
 return self.root.value
 def __iter__(self):
 return self.walk_tree()
 def __len__(self):
 return self.count
 def burn_tree(self):
 while self.root is not None:
 highest_num = self.tree_max(self.root)
 print(highest_num.value)
 self.tree_delete(highest_num.value)
 self.count -= 1

Answer 1

Here's some general critique.

1. Don't call it a BTree -- that's a related but significantly different data structure. Call it a MyBinaryTree.
2. It's not necessary for the methods to all have the word "tree" in them. That just adds wordiness and doesn't help with code readability.
3. Don't use print statements to signal errors. What if your code is used in a situation without a console, such as a batch/background process or GUI? Python has a very good exception mechanism; use it.
4. Don't use print statements for logging progress or debug info; use the built-in logging library.
5. Also, the "already exists" error should exit the function, not break. Throwing an exception already takes care of that.
6. Your preorder_tree_walk and postorder_tree_walk don't work as intended, as is evident from their output. Look carefully at how you recurse.
7. Extra comma here def search_tree_from_root(self, search_type=None, key=None,):
8. Don't use magic numbers to implement an enumeration. Instead use a real enumeration. You'll have to move up to Python 3.4 or later -- which you should do anyway.

• BlooB: Thank you for your help, i will correct the mistakes. for some reason i call in order inside both post-order and pre-order, i fixed thoes.

Answer 2

Python 3.x provides collections.abc which includes Abstract Base Classes useful for defining classes that will emulate certain Python container behavior.

As you have written it, your tree class appears to behave like a MutableSet more than anything else - you can insert and remove items, check for membership, and iterate over all the items.

I suggest you implement the MutableSet interface. You might also try Reversible, and you can certainly include some other iterator types (pre-order, post-order) as specially-named methods.