Binary tree
- Binary tree is a non-linear data structure.
- 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
Output
print(root.left.right.val) # -> 5
print(root.left.left.val) # -> 4
Binary Search tree
- Binary search tree is a type of Binary tree in which nodes are inserted based on two conditions.
- If the node to be inserted is less than the parent then 'insert left'.
- 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())
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]
Applications of Binary trees
- Used in many search applications where data is constantly entering/leaving because binary trees have logarithmic time lookup.
- Binary Space Partition - Used in almost any 3D video game to determine which objects need to be rendered.
Top comments (0)