Binary Search Tree Examples:

C++
C++
Java
Java
Python
Python
PHP
PHP
C#
C#
TypeScript
TypeScript
▸ Binary Search Tree Quick Review

Binary Search Tree in Python


class TreeNode:
   def __init__(self, value, right, left):
       self.value = value
       self.right = right
       self.left = left
   

class BinarySearchTree:

   def __init__(self):
       self.root = None

   def isEmpty(self):
       return self.root is None
   
   def add(self, value):
       if self.root is None:
           self.root = TreeNode(value, None, None)
           return
       self._addRecursive(value, self.root)

   def _addRecursive(self, value, node):
       if value > node.value:
           if node.right is not None:
               self._addRecursive(value, node.right)
           else:
               node.right = TreeNode(value, None, None)
       elif value < node.value:
           if node.left is not None:
               self._addRecursive(value, node.left)
           else:
               node.left = TreeNode(value, None, None)
           
   def contains(self, value):
       if self.root is None:
           return False
       return self._containsRecursive(value, self.root)
   
   def _containsRecursive(self, value, node):
       if node is None:
           return False
       if value > node.value:
           return self._containsRecursive(value, node.right)
       elif value < node.value:
           return self._containsRecursive(value, node.left)
       else:
           return True
   
   def find(self, value):
       if self.root is None:
           return None
       return self._findRecursive(value, self.root)

   def _findRecursive(self, value, node):
       if node is None:
           return None
       
       if value > node.value:
           return self._findRecursive(value, node.right)
       elif value < node.value:
           return self._findRecursive(value, node.left)
       else:
           return node
   
   def remove(self, value):
       if self.root is None:
           return
       else:
           self.root = self._removeRecursive(value, self.root)
   
   def _removeRecursive(self, value, node):

       if node is None:
           return None
       
       if value > node.value:
           node.right = self._removeRecursive(value, node.right)
       elif value < node.value:
           node.left = self._removeRecursive(value, node.left)
       else:
           if node.left is not None and node.right is not None:
               tmp = node
               leftMost = self._getLeftMost(tmp.right)
               node.value = leftMost.value

               self.root.right = self._removeRecursive(leftMost.value, node.right)

           elif node.left is not None:
               node = node.left
           elif node.right is not None:
               node = node.right
           else:
               node = None
               
       return node
   
   def _getLeftMost(self, node):
       if node is None:
           return None
       elif node.left is None:
           return node
       else:
           return self._getLeftMost(node.left)

   def clear(self):
       self.root = None

   def __str__(self):
       return "[" + self.toString(self.root) + "]"

   def toString(self, node):
       res = ""
       if node is None:
           return res
       
       if node.left is not None:
           res += self.toString(node.left)
       res += str(node.value) + " "
       if node.right is not None:
           res += self.toString(node.right)
       return res

Find any bugs in the code? let us know!