# Delete from BSTby Isai Damier, Android Engineer @ Google

```  #=====================================================================
# Author: Isai Damier
# Title: Delete
# Project: geekviewpoint
# Package: algorithms
#
# Time Complexity of Solution:
#   Best = const; Average = O(log(n)); Worst = O(n).
#
# Technical Details:
#    1] find node to be removed and track its parent
#    2] if node is None then return None (element is not in tree)
#    3] declare 'replacement' Node
#    4] if node has both children
#     - delete node's successor
#     - give custody of node's children to successor
#     - set 'replacement' to successor
#    5] if node has fewer than two children
#     - set 'replacement' to node's child
#    6] if node is self.root then set 'replacement' to self.root
#       (new self.root)
#    7] else 'replacement' becomes child of node's parent
#
#=====================================================================

class BST( object ):

def __init__( self ):
self.root = None

def getRoot( self ):
return self.root

def delete( self, el ):
# find node and it's parent
node, parent = self.root, None

while node is not None and el != node.data:
parent = node
if el > node.data:
node = node.right
else:
node = node.left

# if node is None return None
if node is None:
return None

# declare replacement
replacement = None
# if node has two children
if node.left is not None and node.right is not None:
replacement = self.removeSuccessor( node )
replacement.left = node.left
replacement.right = node.right
# if node has one or no child
elif node.left is None:
replacement = node.right
else:
replacement = node.left

# replace node
if node == self.root:
self.root = replacement
elif parent.left == node:
parent.left = replacement
else:
parent.right = replacement

return node

def removeSuccessor( self, n ):
# it is known that n has a right child
succ, parent = n.right, n
while succ.left is not None:
parent = succ
succ = succ.left

# a successor has no left child
if succ == parent.right:
parent.right = succ.right
else:
parent.left = succ.right

return succ
```