Binary tree and BinarySearch tree implementation in Python
Tags: binarytree, python, datastructures
Published: 2021-04-05 10:58:57

# 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

```python
# # # 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
```

#### Output
```python
print(root.left.right.val) # -> 5
print(root.left.left.val)  # -> 4
```


# 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

```python
# # # 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())
```
#### Output

```python
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]
```

**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.