Get startedGet started for free

Inserting a node into a binary search tree

In the video, you learned what binary search trees (BSTs) are and how to implement their main operations.

In this exercise, you will implement a function to insert a node into a BST.

To test your code, you can use the following tree:

Graphical representation of a binary search tree.

The nodes contain titles of books, building a BST based on alphabetical order.

This tree has been preloaded in the bst variable:

bst = CreateTree()

You can check if the node is correctly inserted with this code:

bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))

This exercise is part of the course

Data Structures and Algorithms in Python

View Course

Exercise instructions

  • Check if the BST is empty.
  • Check if the data to insert is smaller than the current node's data.
  • Check if the data to insert is greater than the current node's data.

Hands-on interactive exercise

Have a go at this exercise by completing this sample code.

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

  def insert(self, data):
    new_node = TreeNode(data)
    # Check if the BST is empty
    if ____ == None:
      self.root = new_node
      return
    else:
      current_node = self.root
      while True:
        # Check if the data to insert is smaller than the current node's data
        if ____ < ____:
          if current_node.left_child == None:
            current_node.left_child = new_node
            return 
          else:
            current_node = current_node.left_child
        # Check if the data to insert is greater than the current node's data
        elif ____ > ____:
          if current_node.right_child == None:
            current_node.right_child = new_node
            return
          else:
            current_node = current_node.right_child

bst = CreateTree()
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Edit and Run Code