Python Tree Data Structure- Binary Search Tree

Binary Search Tree is a non linear data structure that arranges elements in a certain pattern. In this Python Tree Data Structure if a new element’s value is less than current node’s data value, it is added in its left subtree. If new element’s value is greater than current node’s value, it must be added in its right subtree.

The exact position of insertion is found by comparing the value to be inserted from root to a leaf node. At each step it is compared with the current node. If smaller than the current node follow left subtree else follow right subtree. Repeat this process till it is located in BST or pointer returns NULL.

A Binary Search Tree is a good choice for sorting and storing indexes for efficient searching. Search performance of a BST is same as that of a Binary Search Algorithm O(log(n)).

Insertion in Binary Search Tree

Let the element to be inserted is ITEM
Create a new node NODE with ITEM as its data part
Initialize CURR with root of Binary Search Tree and PAR with None
Search ITEM in the Binary Search Tree till the item is found or we reach a leaf node without finding ITEM
1. If ITEM matches the CURR ->DATA return PAR and CURR as address of parent node and current node respectively. Exit Insert operation since ITEM already exists
1. If ITEM <CURR->DATA set PAR= CURR and CURR=CURR->LEFT to proceed to left subtree and find the location where the new node is to be inserted.
1. If ITEM >CURR->DATA set PAR= CURR and CURR=CURR->RIGHT to proceed to right subtree and find the location where the new node is to be inserted.
Insert the new node as child of PAR by setting
1. PAR->LEFT = NODE if ITEM <PAR->DATA or PAR->RIGHT = NODE if ITEM >PAR->DATA

Deletion in Binary Search Tree

Let the element to be deleted is ITEM.
Initialize CURR with root of Binary Search Tree and PAR with None
Search ITEM in the Binary Search Tree and get PAR (parent) and CURR(Item).
If ITEM is a leaf node or a one-child parent node, delete it by setting LEFT or RIGHT pointers of parent node identified as PAR with appropriate value
If ITEM is an internal node
1. Find its INORDER successor SUC and successor’s parent PARSUC
1. Delete successor SUC as in Step 4
1. Replace ITEM with SUC by updating its parent’s pointer with SUC and its LEFT and RIGHT pointers with CURR’s LEFT and RIGHT pointers.

Traversals in Binary Search Tree

InOrder Traversal

Traverse left subtree in InOrder
Process the Node
Traverse right subtree in InOrder

PreOrder Traversal

Process the Node
Traverse left subtree in PreOrder
Traverse right subtree in PreOrder

PostOrder Traversal

Traverse left subtree in PostOrder
Traverse right subtree in PostOrder
Process the Node

Python Tree Data Structure BST – Code

#Python Tree Data Structure- Binary Search Tree code with user defined
#classes  Node and BinarySearchTree
class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data=data
        self.left=left
        self.right=right
    def __str__(self):
        return str(self.data)

class BinarySearchTree:
    def __init__(self, root=None):
        self.root=root
        self.str=""
    def addNode(self, value=None):
        node=Node(value)
        par=None
        if self.root==None:
            print("Rood added ->",value)
            self.root=node
        else:
            curr=self.root
            while curr:
                
                if curr.data==value:
                    break
                elif curr.data>value:
                    par=curr
                    curr=curr.left
                else:
                    par=curr
                    curr=curr.right
            if value>par.data:
                print("Adding in right of ",par.data," new node ", value)
                par.right=node
            else:
                print("Adding in left of ",par.data," new node ", value)
                par.left=node
    def delNode(self, value=None):
        curr=self.root
        par=None
        
        while curr:
            if curr.data==value:
                if (curr.left!= None) and (curr.right!=None):
                    self.twochild(par,curr)
                    return
                else:    
                    self.onechild(par,curr)
                    return
            elif value>curr.data:
                par=curr
                curr=curr.right
            else:
                par=curr
                curr=curr.left

    def onechild(self, par=None,ptr=None):
        if ptr.left!=None:
            child=ptr.left
        elif ptr.right!=None:
            child=ptr.right
        else:
            child=None

        if ptr==par.left:
            par.left=child
        else:
            par.right=child
       
    def twochild(self, par=None,ptr=None):
        parsuc=ptr
        suc=ptr.right
        while suc.link:
            parsuc=suc
            suc=suc.link

        onechild(parsuc,suc)  

        suc.left=ptr.left
        suc.right=ptr.right
        if ptr==par.left:
            par.left=suc
        else:
            par.right=suc
            
                
    def InTrav(self, ptr=None):
        curr=ptr
        if (curr):
            self.InTrav(curr.left)
            print(curr.data)
            self.InTrav(curr.right)
    def PreTrav(self, ptr=None):
        curr=ptr
        if (curr):
            print(curr.data)
            self.InTrav(curr.left)
            self.InTrav(curr.right)           
    def PostTrav(self, ptr=None):
        curr=ptr
        if (curr):
            self.InTrav(curr.left)
            self.InTrav(curr.right)
            print(curr.data)
           

bst= BinarySearchTree()
inval=str(input("Enter the value for BST separated by commas"))
inarr=inval.split(",")
for i in range(len(inarr)):
    bst.addNode(int(inarr[i]))
print("Traversal in Inorder")
bst.InTrav(bst.root)
print("Traversal in Preorder")
bst.PreTrav(bst.root)            
print("Traversal in Postorder")
bst.PostTrav(bst.root)
inval=int(input("Enter the value to be deleted:"))
bst.delNode(inval)
print("Traversal after deletion")
bst.InTrav(bst.root)

admin