Exercise

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"))

Instructions

100 XP
  • 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.