# 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

1. Let the element to be inserted is ITEM
2. Create a new node NODE with ITEM as its data part
3. Initialize CURR  with root of Binary Search Tree and PAR with None
4. 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.
5. 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

1. Let the element to be deleted is ITEM.
2. Initialize CURR  with root of Binary Search Tree and PAR with None
3. Search ITEM in the Binary Search Tree and get PAR (parent) and CURR(Item).
4. 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
5. 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

1. Traverse left subtree in InOrder
2. Process the Node
3. Traverse right subtree in InOrder

#### PreOrder Traversal

1. Process the Node
2. Traverse left subtree in PreOrder
3. Traverse right subtree in PreOrder

#### PostOrder Traversal

1. Traverse left subtree in PostOrder
2. Traverse right subtree in PostOrder
3. 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=""
node=Node(value)
par=None
if self.root==None:
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
parsuc=suc

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)):
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)

```