Skip to content

Latest commit

 

History

History
353 lines (289 loc) · 7.25 KB

OperationOnBST.md

File metadata and controls

353 lines (289 loc) · 7.25 KB
Raw

Operation on Binary Search Tree

Binary Search Tree Operations

1. Insert Element
2. Traverse Tree
    i.Inorder Traversal
    ii.Preorder Traversal
    iii.Postorder Traversal
    
3. Search Element
4. Remove Element

1. Insert Element

  • Use Recursive pattern to insert new Item in Binary Search Tree Follow steps to insert new items in the tree.

  • Craete a Normal Node class to creates Nodes for building of Binary search tree

class Node:
  def __init__(self,value=None):
    self.value=value
    self.left=None
    self.right=None
    self.count = 1
  • Create class BST and create Insert and Insert Method Respectively
class BST:
    def Insert(self,root,value):
        #create Node using value
        node=Node(value)

        #Perform Insertion Operation here in Recursive manner
        if the root is None Then Return node

        if the root node is not None then perform the following operation
            if root.value==value then just increase counter by 1
            elif value<root.value then assign root.left=self.Insert(root.left,value)
            elif value>root.value then assign root.right=self.Insert(root.right,value)

        #finally return root node
        return root

and call above function method from a wraper Method

 def InsertWrap(self,data):
     root=Node(data[0])
     for value in data[1:]:
        root=self.Insert(root,value)
     #Return the root node
     return node
  • now create Object of BST
t=BST()
data=[9,6,16,18,1,4,7]
t.InsertWrap(data)

Full Methods :

#Recusrsive Function to Insert Data into Tree
def Insert(self,root,value):
    node=Node(value)
    if root is None:
      return node
    else:
      if root.value==value:
        root.count+=1
      elif value<root.value:
        root.left=self.Insert(root.left,value)
      elif value>root.value:
        root.right=self.Insert(root.right,value)
    return root

#Wraper Function to Call Insert Method (Call this method first using class object)
def Insertwrap(self,data):
    root=Node(data[0])
    print("Root Node assigned ",data[0])
    for value in data[1:]:
      root=self.Insert(root,value)
      print("Inserted Node",value)
    return root

2. Traverse Tree

i.Inorder Traversal

Simple Steps for Inorder Traversal

  1. visit the left node if exists
  2. print root node Value
  3. visit right node if exists
  4. go to step 1 if the root node is exists

Example(Recusrsive):

def InOrder(self,root,array):
    if root:
      self.InOrder(root.left,array)
      array.append(root.value)
      self.InOrder(root.right,array)
    return array

ii.Preorder Traversal

Simple Steps for Preorder Traversal

  1. print root node Value
  2. visit left node if exists
  3. visit right node if exists
  4. go to step 1 if the root node is exists

Example(Recursive):

def PreOrder(self,root,array):
    if root:
      array.append(root.value)
      self.PreOrder(root.left,array)
      self.PreOrder(root.right,array)
    return array

iii.Postorder Traversal

  1. visit the right node if exists
  2. visit left node if exists
  3. print root node Value
  4. go to step 1 if the root node is exists

Example(Recursive):

 def PostOrder(self,root,array):
    if root:
      self.PostOrder(root.left,array)
      self.PostOrder(root.right,array)
      array.append(root.value)
    return array

3. Search Element

Use the following steps to search an element in Binary Search Tree consider

root=Your_binary_search_tree
value=search_element
  1. if root.value==value then simple return True
  2. else compare value with root.value
  3. if value<root.value and root.left is present then return Find(root.left,value) root.left is not present then return False
  4. if value>root.value and root.right is present then return Find(root.right,value) root.right is not present then return False

Example:

def Find(self,root,value):
    if root.value==value:
      return True
    else:
      if value<root.value:
        if root.left:
          return self.Find(root.left,value)
        else:
          return False
      else:
        if root.right:
          return self.Find(root.right,value)
        else:
          return False

Following Example Contains

Insert Element
Inorder Traversal
Preorder Traversal
Postorder Traversal
Search Element

Example

class Node:
  def __init__(self,value=None):
    self.value=value
    self.left=None
    self.right=None
    self.count = 1
    
class Tree:
  def __init__(self):
    self.root=None
  
  def Insert(self,root,value):
    node=Node(value)
    if root is None:
      return node
    else:
      if root.value==value:
        root.count+=1
      elif value<root.value:
        root.left=self.Insert(root.left,value)
      elif value>root.value:
        root.right=self.Insert(root.right,value)
    return root
  
  def Insertwrap(self,data):
    root=Node(data[0])
    print("Root Node assigned ",data[0])
    for value in data[1:]:
      root=self.Insert(root,value)
      print("Inserted Node",value)
    return root

  def Find(self,root,value):
    if root.value==value:
      return True
    else:
      if value<root.value:
        if root.left:
          return self.Find(root.left,value)
        else:
          return False
      else:
        if root.right:
          return self.Find(root.right,value)
        else:
          return False
          
  def PreOrder(self,root,array):
    if root:
      array.append(root.value)
      self.PreOrder(root.left,array)
      self.PreOrder(root.right,array)
    return array        
          
  def InOrder(self,root,array):
    if root:
      self.InOrder(root.left,array)
      array.append(root.value)
      self.InOrder(root.right,array)
    return array
    
  def PostOrder(self,root,array):
    if root:
      self.PostOrder(root.left,array)
      self.PostOrder(root.right,array)
      array.append(root.value)
    return array
      

data=[9,6,16,18,1,4,7]
t=Tree()
print("\n_________ Insertion of Node Through List________________")

root=t.Insertwrap(data)
'''
This Binary Search Tree Is Generated Finally

     9
    / \
   6   16
  / \    \
 1   7    18
  \    
   4   

     _9_
    /   \
  _6_    16_
 /   \        \
 1_   7      18
   \    
    4 
       
'''


print("\n___________ Different Tree Traversal_____________________")

print("\nPre Order Traversal")
result=[]
t.PreOrder(root,result)
print(result)

print("\nIn Order Traversal (Sorted)")
result=[]
t.InOrder(root,result)
print(result)

print("\nPost Order Traversal")
result=[]
t.PostOrder(root,result)
print(result)



print("\n___________ Search Element In Tree _____________________")

print("\nIs 4 Present in tree ")
ispresent=t.Find(root,4)
print(ispresent)

print("\nIs 5 Present in tree ")
ispresent=t.Find(root,5)
print(ispresent)

Output:

_________ Insertion of Node Through List________________

Root Node assigned  9
Inserted Node 6
Inserted Node 16
Inserted Node 18
Inserted Node 1
Inserted Node 4
Inserted Node 7

___________ Different Tree Traversal_____________________

Pre Order Traversal
[9, 6, 1, 4, 7, 16, 18]

In Order Traversal (Sorted)
[1, 4, 6, 7, 9, 16, 18]

Post Order Traversal
[4, 1, 7, 6, 18, 16, 9]

___________ Search Element In Tree _____________________

Is 4 Present in tree 
True

Is 5 Present in tree 
False