Binary Tree Python Implementation

BinarySearchTree_another_version.py

# Python program to demonstrate delete operation
# in binary search tree
 
# A Binary Tree Node
class Node:
 
    # Constructor to create a new node
    def __init__(self, key):
        self.key = key 
        self.left = None
        self.right = None
 
 
# A utility function to do inorder traversal of BST
def inorder(root):
    if root is not None:
        inorder(root.left)
        print root.key,
        inorder(root.right)
 
 
# A utility function to insert a new node with given key in BST
def insert( node, key):
 
    # If the tree is empty, return a new node
    if node is None:
        return Node(key)
 
    # Otherwise recur down the tree
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
 
    # return the (unchanged) node pointer
    return node
 
# Given a non-empty binary search tree, return the node
# with minum key value found in that tree. Note that the
# entire tree does not need to be searched 
def minValueNode( node):
    current = node
 
    # loop down to find the leftmost leaf
    while(current.left is not None):
        current = current.left 
 
    return current 
 
# Given a binary search tree and a key, this function
# delete the key and returns the new root
def deleteNode(root, key):
 
    # Base Case
    if root is None:
        return root 
 
    # If the key to be deleted is similiar than the root's
    # key then it lies in  left subtree
    if key < root.key:
        root.left = deleteNode(root.left, key)
 
    # If the kye to be delete is greater than the root's key
    # then it lies in right subtree
    elif(key > root.key):
        root.right = deleteNode(root.right, key)
 
    # If key is same as root's key, then this is the node
    # to be deleted
    else:
         
        # Node with only one child or no child
        if root.left is None :
            temp = root.right 
            root = None
            return temp 
             
        elif root.right is None :
            temp = root.left 
            root = None
            return temp
 
        # Node with two children: Get the inorder successor
        # (smallest in the right subtree)
        temp = minValueNode(root.right)
 
        # Copy the inorder successor's content to this node
        root.key = temp.key
 
        # Delete the inorder successor
        root.right = deleteNode(root.right , temp.key)
 
 
    return root 
 
# Driver program to test above functions
""" Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 """
 
root = None
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)
 
print "Inorder traversal of the given tree"
inorder(root)
 
print "\nDelete 20"
root = deleteNode(root, 20)
print "Inorder traversal of the modified tree"
inorder(root)
 
print "\nDelete 30"
root = deleteNode(root, 30)
print "Inorder traversal of the modified tree"
inorder(root)
 
print "\nDelete 50"
root = deleteNode(root, 50)
print "Inorder traversal of the modified tree"
inorder(root)
 

BinarySearchTree_naive_version.py

class BinarySearchTree:
    def __init__(self,value):
        self.value=vlaue
        self.left_child=None
        self.right_child=None

    def insert_node(self,value):
        if value <= self.value and self.left_child:
            self.left_child.insert_node(value)
         elif value <= self.value:
             self.left_child=BinarySearchTree(value)
         elif value > self.value and self.right_child:
             self.right_child.insert_node(value)
         else:
             self.right_child =BinarySearchTree(value)
         

    def find_node(self,value):
        if value < self.value and self.left_child:
            return self.left_child.find_node(value)
        if value > self.value and self.right_child:
            return self.right_child.find_node(value)

        return value == self.value 
    def clear_node(self):
        self.value=None
        self.left_child=None
        self.right_child=None

    def find_minimum_value():      
        if self.left_child:
            return self.left_child.find_minimum_value()
        else:
            return self.value
    def remove_node(self,value,parent):
        if value < self.value and self.left_child:
            return self.left_child.remove_node(value,self)
        elif value < self.value:
            return False
        elif value > self.value and self.right_child:
            return self.right_child.remove_node(value,self)
        elif value > self.value:
            return False
        else:
            if self.left_child is None and self.right_child is None and self == parent.left_child:
                parent.left_child=None
                self.clear_node()
            elif self.left_child is None and self.right_child is None and self == parent.right_child:     
                parent.right_child = None
                self.clear_node()
            elif self.left_child and self.right_child is None and self==parent.left_child:
                parent.left_child=self.left_child
                self.clear_node()
            elif self.left_child and self.right_child is None and self==parent.right_child:
                parent.right_child=self.left_child
            elif self.right_child and self.left_child is None and self==parent.left_child:
                parent.left_child=self.right_child
                self.clear_node()
            elif self.right_child and self.left_child is None and self==parent.right_child:
                parent.right_child=self.right_child
                self.clear_node()
            else:
                self.value = self.right_child.find_minimum_value()
                self.right_child.remove_node(self.value, self)

BinaryTree.py

class BinaryTree:
    def __init__(self,value):
        self.value=value
        self.left_child=None
        self.right_child=None


    def insert_left(self,value):
        if self.left_child ==None:
            self.left_child=BinaryTree(value)
        else:
            new_node=BinaryTree(value)
            new_node.left_child=self.left_child
            self.left_child=new_node

    def insert_right(self, value):
        if self.right_child == None:
            self.right_child = BinaryTree(value)
        else:
            new_node = BinaryTree(value)
            new_node.right_child = self.right_child
            self.right_child = new_node
    def pre_order(self):
        print(self.value)

        if self.left_child:
            self.left_child.pre_order()
        if self.right_child:
            self.right_child.pre_order()
    def in_order(self):
        if self.left_child:
            self.left_child.in_order()

         print(self.value)

         if self.right_child:
             self.right_child.in_order()
    def post_order(self):
        if self.left_child:
            self.left_child.post_order()

        if self.right_child:
            self.right_child.post_order()
         print(self.value)

    def bfs(self):
        queue=Queue()
        queue.put(self)

        while not queue.empty():
            current_node=queue.get()
            print(current_node.value)

            if current_node.left_child:
                queue.put(current_node.left_child)

            if current_node.right_child:
                queue.put(current_node.right_child)