DEV Community

Cover image for Binary tree and BinarySearch tree implementation in Python
Karhik Suryadevara
Karhik Suryadevara

Posted on • Updated on

Binary tree and BinarySearch tree implementation in Python

Binary tree

  1. Binary tree is a non-linear data structure.
  2. In a binary tree each node has at most '2' children.

Code to implement Binary tree

# # # Binary tree
class treeNode:
    def __init__(self,val = None):
        self.val = val
        self.left = None
        self.right = None

root = treeNode(1)
root.left = treeNode(2)
root.right = treeNode(3)
# #       1
# #     /  \
# #    2    3
root.left.left = treeNode(4)
root.left.right = treeNode(5)
# #           1
# #         /  \
# #        2    3
# #       / \
# #      4   5
Enter fullscreen mode Exit fullscreen mode

Output

print(root.left.right.val) # -> 5
print(root.left.left.val)  # -> 4
Enter fullscreen mode Exit fullscreen mode

Binary Search tree

  1. Binary search tree is a type of Binary tree in which nodes are inserted based on two conditions.
  2. If the node to be inserted is less than the parent then 'insert left'.
  3. If the node to be inserted is more than the parent then 'insert right'.

Code to implement Binary Search Tree

# # # Binary search tree
class binarySearchTree:
    def __init__(self,val=None):
        self.val = val
        self.left = None
        self.right = None

    def insert(self,val):
        # check if there is no root
        if (self.val == None):
            self.val = val
        # check where to insert
        else:
            # check for duplicate then stop and return
            if val == self.val: return 'no duplicates aloowed in binary search tree'
            # check if value to be inserted < currentNode's value
            if (val < self.val):
                # check if there is a left node to currentNode if true then recurse
                if(self.left):
                    self.left.insert(val)
                # insert where left of currentNode when currentNode.left=None
                else: self.left = binarySearchTree(val)

            # same steps as above here the condition we check is value to be inserted > currentNode's value
            else:
                if(self.right):
                    self.right.insert(val)
                else: self.right = binarySearchTree(val)




    def breadthFirstSearch(self):
        currentNode = self
        bfs_list = []
        queue = []
        queue.insert(0,currentNode)
        while(len(queue) > 0):
            currentNode = queue.pop()
            bfs_list.append(currentNode.val)
            if(currentNode.left):
                queue.insert(0,currentNode.left)
            if(currentNode.right):
                queue.insert(0,currentNode.right)

        return bfs_list

    # In order means first left child, then parent, at last right child
    def depthFirstSearch_INorder(self):
        return self.traverseInOrder([])

    # Pre order means first parent, then left child, at last right child
    def depthFirstSearch_PREorder(self):
        return self.traversePreOrder([])

    # Post order means first left child, then right child , at last parent
    def depthFirstSearch_POSTorder(self):
        return self.traversePostOrder([])

    def traverseInOrder(self, lst):
        if (self.left):
            self.left.traverseInOrder(lst)
        lst.append(self.val)
        if (self.right):
            self.right.traverseInOrder(lst)
        return lst

    def traversePreOrder(self, lst):
        lst.append(self.val)
        if (self.left):
            self.left.traversePreOrder(lst)
        if (self.right):
            self.right.traversePreOrder(lst)
        return lst

    def traversePostOrder(self, lst):
        if (self.left):
            self.left.traversePostOrder(lst)
        if (self.right):
            self.right.traversePostOrder(lst)
        lst.append(self.val)
        return lst

    def findNodeAndItsParent(self,val, parent = None):
        # returning the node and its parent so we can delete the node and reconstruct the tree from its parent
        if val == self.val: return self, parent
        if (val < self.val):
            if (self.left):
                return self.left.findNodeAndItsParent(val, self)
            else: return 'Not found'
        else:
            if (self.right):
                return  self.right.findNodeAndItsParent(val, self)
            else: return 'Not found'

    # deleteing a node means we have to rearrange some part of the tree
    def delete(self,val):
        # check if the value we want to delete is in the tree
        if(self.findNodeAndItsParent(val)=='Not found'): return 'Node is not in tree'
        # we get the node we want to delete and its parent-node from findNodeAndItsParent method
        deleteing_node, parent_node = self.findNodeAndItsParent(val)
        # check how many children nodes does the node we are going to delete have by traversePreOrder from the deleteing_node
        nodes_effected = deleteing_node.traversePreOrder([])
        # if len(nodes_effected)==1 means, the node to be deleted doesn't have any children
        # so we can just check from its parent node the position(left or right) of node we want to delete
        # and point the position to 'None' i.e node is deleted
        if (len(nodes_effected)==1):
            if (parent_node.left.val == deleteing_node.val) : parent_node.left = None
            else: parent_node.right = None
            return 'Succesfully deleted'
        # if len(nodes_effected) > 1 which means the node we are going to delete has 'children',
        # so the tree must be rearranged from the deleteing_node
        else:
            # if the node we want to delete doesn't have any parent means the node to be deleted is 'root' node
            if (parent_node == None):
                nodes_effected.remove(deleteing_node.val)
                # make the 'root' nodee i.e self value,left,right to None,
                # this means we need to implement a new tree again without the delted node
                self.left = None
                self.right = None
                self.val = None
                # construction of new tree
                for node in nodes_effected:
                    self.insert(node)
                return 'Succesfully deleted'

            # if the node we want to delete has a parent
            # traverse from parent_node
            nodes_effected = parent_node.traversePreOrder([])
            # deleting the node
            if (parent_node.left == deleteing_node) : parent_node.left = None
            else: parent_node.right = None
            # removeing the parent_node, deleteing_node and inserting the nodes_effected in the tree
            nodes_effected.remove(deleteing_node.val)
            nodes_effected.remove(parent_node.val)
            for node in nodes_effected:
                self.insert(node)

        return 'Successfully deleted'


bst = binarySearchTree()
bst.insert(7)
bst.insert(4)
bst.insert(9)
bst.insert(0)
bst.insert(5)
bst.insert(8)
bst.insert(13)

#          7
#        /  \
#      /     \
#     4        9
#    / \      /  \
#   0   5    8    13


print('IN order: ',bst.depthFirstSearch_INorder()) # useful in sorting the tree in ascending order
print('PRE order:' ,bst.depthFirstSearch_PREorder()) # pre order is useful in reconstructing a tree
print('POST order:', bst.depthFirstSearch_POSTorder()) # useful in finding the leaf nodes

print(bst.delete(5))
print(bst.delete(9))
print(bst.delete(7))

# after deleting
print('IN order: ',bst.depthFirstSearch_INorder())
Enter fullscreen mode Exit fullscreen mode

Output

IN order:  [0, 4, 5, 7, 8, 9, 13]

PRE order: [7, 4, 0, 5, 9, 8, 13]

POST order: [0, 5, 4, 8, 13, 9, 7]

Successfully deleted
Successfully deleted
Successfully deleted

IN order:  [0, 4, 8, 13]
Enter fullscreen mode Exit fullscreen mode

Applications of Binary trees

  1. Used in many search applications where data is constantly entering/leaving because binary trees have logarithmic time lookup.
  2. Binary Space Partition - Used in almost any 3D video game to determine which objects need to be rendered.

Top comments (0)