# DSA Binary Search Tree A Binary Search Tree is a special Binary tree (each parent node can have maximum 2 node), which satisfy the following condition.

• The tree must be a binary search tree.
• The left sub-tree key value should be less than the parent node key value.
• The right-sub tree key value should be greater than the parent node key value.

If a tree satisfies the above 3 conditions then it would be considered as a Binary Search Tree.

### Binary Search Tree Representation

Let’s represent a binary search tree which keys values are [31,16,61,8,23,46,77,19,28]

```                        31
/  \
/    \
16     61
/   \   /  \
8    23  46  77
/ \
19  29```

The binary tree is a Binary Search tree because each node has 2 or less than 2 child nodes, and each parent node left child is smaller than the parent node and the right child is greater than the parent node.

### Advantages of Binary Search Tree

• It optimizes the searching algorithm, as we know that the elements on the right side are greater than the parent node and elements on the left side are smaller than the parent node so, with simple comparison, we can search any element efficiently.
• The insertion of the new element in a binary search tree is also very easy.
• If we compare it with the linked list and array it is more efficient.

### Complexities

 Algorithms Average Complexity Worst Complexity Space O(n) O(n) Search O(log n) O(n) Insert O(log n) O(n) Delete O(log n) O(n)

### Basic Operations on Binary Search Tree

Like other data structure we can perform some basic operations on Binary Search Tree:

• Insertion
• Deletion
• Traversal
• Searching

#### Insertion

In BST the insertion takes place always at the bottom of a tree. No matter what the new element inserted in the tree become the leaf node of the tree. Suppose we have a tree:

```                        31
/  \
/    \
16     61```

#### Insert

100 is greater than root node 31 so it lay on the right subtree of the tree. But 31 already has a right child 61, so now we will compare the right child of the parent node with the new element 100.

```                        31
/  \
/    \
16     61
```

The right subtree has already a node 61 so we will compare 100 with 61, and 100 is greater than 61 so it resides as the right child of 61 because 61 does not have any child.

```                        31
/  \
/    \
16     61
\
100```

#### Insertion algorithm

```def insert(key,data,currentnode):
if not root:
root = Node(key,data)
else:
if key < root.key:
if currentnode.hasLeftChild():
insert(key,data,currentnode.leftchild)
else:
currentnode.leftChild = Node(key,data)
else:
if currentnode.hasLeftChild():
insert(key,data,currentnode.leftchild)
else:
currentnode.leftChild = Node(key,data)
```

#### Deletion

Deletion is the most complex and lengthy operation of BST, when we perform the deletion operation, we have to take care of three conditions.

• The node we have to delete is a leaf node
• The node we have to delete has only one child.
• The node we have to delete has 2 child nodes.

#### Traversal

Like a binary tree, we can use any of the tree traversal methods on BST to visits each node. Those three methods are

• Pre-Order Traversal
• In-Order Traversal
• Post-Order Traversal.

#### Searching

To retrieve the data of any particular node we can perform the search operation on the Binary search tree. To search the data, we use the corresponding key value.

### Implementation of Binary Search Tree

#### In Python

Here we will use python to implement a Binary Search Tree. We use the class to create the structure for binary search tree and use node to create specific nodes that will reside in the BST.

```class Node:
def __init__(self,key,val,left=None,right=None,parent=None):
self.key = key
self.data = val
self.leftChild = left
self.rightChild = right
self.parent = parent
def hasLeftChild(self):
return self.leftChild
def hasRightChild(self):
return self.rightChild
def isLeftChild(self):
return self.parent and self.parent.leftChild == self
def isRightChild(self):
return self.parent and self.parent.rightChild == self
def isRoot(self):
return not self.parent
def isLeaf(self):
return not (self.rightChild or self.leftChild)
def hasAnyChildren(self):
return self.rightChild or self.leftChild
def hasBothChildren(self):
return self.rightChild and self.leftChild
def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.data = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self
class BinarySearchTree:

def __init__(self):
self.root = None
self.size = 0

def length(self):
return self.size

def __len__(self):
return self.size

def insert(self,key,val):
if self.root:
self._insert(key,val,self.root)
else:
self.root = Node(key,val)
self.size = self.size + 1

def _insert(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._insert(key,val,currentNode.leftChild)
else:
currentNode.leftChild = Node(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._insert(key,val,currentNode.rightChild)
else:
currentNode.rightChild = Node(key,val,parent=currentNode)

def __setitem__(self,k,v):
self.insert(k,v)

def search(self,key):
if self.root:
res = self._search(key,self.root)

if res:
return res.data
else:
return None
else:
return None

def _search(self,key,currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._search(key,currentNode.leftChild)
else:
return self._search(key,currentNode.rightChild)

def __searchitem__(self,key):
return self.search(key)

def __contains__(self,key):
if self._search(key,self.root):
return True
else:
return False

def delete(self,key):
if self.size > 1:
nodeToRemove = self._search(key,self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self.size-1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError('Error, key not in tree')

def __delitem__(self,key):
self.delete(key)

def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None

elif self.hasAnyChildren():
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent

else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent

def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ

def findMin(self):

current = self
while current.hasLeftChild():
current = current.leftChild
return current

def remove(self,currentNode):
if currentNode.isLeaf(): #leaf
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren(): #interior
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.data = succ.data
else: # this node has one child
if currentNode.hasLeftChild():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild

else:
currentNode.replaceNodeData(currentNode.leftChild.key,
currentNode.leftChild.data,
currentNode.leftChild.leftChild,
currentNode.leftChild.rightChild)
else:

if currentNode.isLeftChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
else:
currentNode.replaceNodeData(currentNode.rightChild.key,
currentNode.rightChild.data,
currentNode.rightChild.leftChild,
currentNode.rightChild.rightChild)```