Binary Search Tree (BST)

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Definition

Left subtree of a node:
- values less than the node itself
Right subtree of a node:
- values greater than the node itself
Left and right subtrees must be binary search trees

Schematic representation of a binary search tree.

Implementation

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

class BinarySearchTree:
  def __init__(self):
    self.root = None

Searching

Search for 72

Schematic representation of a binary search tree.

Searching

Search for 72

Schematic representation of a binary search tree where the root node is colored in yellow.

Searching

Search for 72

Schematic representation of a binary search tree where the root node and the left subtree of the root node are also colored in gray. The first node of the right subtree is colored in yellow.

Searching

Search for 72

Schematic representation of a binary search tree. The left subtree of the last root node and the last root node are also colored in gray. The new root node is colored in yellow.

Searching

Search for 72

Schematic representation of a binary search tree where the new root node is colored in yellow and the rest of the nodes are colored in gray.

Searching

Search for 72

Schematic representation of a binary search tree where the new root node is colored in yellow and the rest of the nodes are colored in gray. The colored node has the number 72 and is highlighted.

Searching

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

Inserting

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Graphical representation of a new node.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

Graphical representation of the new node that has become the root node.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

Graphical representation of a new node and a root node with a right child.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

Graphical representation of a new node and a root node with a right child. The root node is the current_node.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

Graphical representation of a root node with a right child and left child. The root node is the current_node. The new node is the left child.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

Graphical representation of a new node and binary search tree with some elements. The root node is the current_node.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

Graphical representation of a new node and binary search tree with some elements. The current_node is the root's left child.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

Graphical representation of a new node and binary search tree with a left subtree.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

Graphical representation of a binary search tree with a left subtree. The new node is now the root's right child.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

Graphical representation of a new node and binary search tree some elements.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Graphical representation of a new node and binary search tree with some elements. The current_node is the root's right child.

Inserting

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Graphical representation of a new node and binary search tree with some elements. The current_node is the root's right child. The new node is the current_node's left child.

Deleting

No children

Graphical representation of a binary search tree with some elements. One of the nodes is colored in red because it is going to be removed. This node has no children.

Deleting

No children
- delete it

Graphical representation of a binary search tree with some elements. The node that was going to be removed has disappeared from the tree.

Deleting

One child

Graphical representation of a binary search tree with some elements. One of the nodes is colored in red because it is going to be removed. This node has a right child.

Deleting

One child
- delete it
- connect the child with node's parent

Graphical representation of a binary search tree with some elements. The node that was going to be removed has disappeared from the tree and the root node points to the removed node's right child.

Deleting

One child
- delete it
- connect the child with node's parent

Graphical representation of a binary search tree.

Deleting

Two children

Graphical representation of a binary search tree where the root node is going to be deleted and is colored in red.

Deleting

Two children
- replace it with its successor
  - the node with the smallest value greater than the value of the node
- find the successor:

Graphical representation of a binary search tree where the root node is going to be deleted and is colored in red.

Deleting

Two children
- replace it with its successor
  - the node with the least value greater than the value of the node
- find the successor:
  - visit the right child

Graphical representation of a binary search tree where the root node is going to be deleted and is colored in red. The root's right child is colored in yellow.

Deleting

Two children
- replace it with its successor
  - the node with the least value greater than the value of the node
- find the successor:
  - visit the right child
  - keep visiting the left nodes until the end

Graphical representation of a binary search tree where the root node is going to be deleted and is colored in red. Another node is colored in yellow in order to find the successor.

Deleting

Two children
- replace it with its successor
  - the node with the least value greater than the value of the node
- find the successor:
  - visit the right child
  - keep visiting the left nodes until the end

Graphical representation of a binary search tree where the root node is going to be deleted and is colored in red. Another node is colored in yellow in order to find the successor.

Deleting

Two children
- replace it with its successor
  - the node with the least value greater than the value of the node
- find the successor:
  - visit the right child
  - keep visiting the left nodes until the end

Graphical representation of a binary search tree where the root node is going to be deleted and is colored in red. Another node is colored in yellow in order to find the successor. The successor has been found and it is the number 13.

Deleting

Two children
- replace it with its successor
  - the node with the least value greater than the value of the node
- find the successor:
  - visit the right child
  - keep visiting the left nodes until the end

Graphical representation of a binary search tree. The root node has been replaced with the successor.

Deleting

Two children
- replace it with its successor
  - the node with the least value greater than the value of the node
- find the successor:
  - visit the right child
  - keep visiting the left nodes until the end
  - if the successor has a right child:

Graphical representation of a binary search tree where the successor node has a right child.

Deleting

Two children
- replace it with its successor
  - the node with the least value greater than the value of the node
- find the successor:
  - visit the right child
  - keep visiting the left nodes until the end
  - if the successor has a right child:
    - child becomes the left child of successor's parent.

Graphical representation of a binary search tree where the successor node had a right child. The successor child has become the left child of the successor's parent and the root node has been replaced with the successor node.

Uses

Order lists efficiently
Much faster at searching than arrays and linked lists
Much faster at inserting and deleting than arrays
Used to implement more advanced data structures:
- dynamic sets
- lookup tables
- priority queues

Let's practice!

Data Structures and Algorithms in Python