Learn

When inserting a new value into a Binary Search Tree, we compare it with the root node’s value. We will implement an .insert() method in the BinarySearchTree class, assuming that we call the method from a root node like so:

root_node.insert(new_node)

Here’s how insertion will work:

If a new value is less than the current (root) node’s value, we want to insert it to its left subtree.

  • If a left child of the current node doesn’t already exist, we create a new BinarySearchTree node with that value as this node’s left child.
  • If a left child already exists, we would call .insert() recursively on the current node’s left child to insert further down.

If a new value is not less than the current (root) node’s value, we’ll want to insert it as a descendant on the right side. The logic for this will be similar:

  • If a right child of the current node doesn’t already exist, we create a new BinarySearchTree node with that value as this node’s right child.
  • If a right child already exists, we would call .insert() recursively on the current node’s right child.

The pseudocode for the insertion procedure is as follows:

If the new value is less than the root node's value
  If a left child node does not exist
    Create a new BinarySearchTree with the new value and updated depth and assign it to the left pointer
  Else
    Recursively call .insert() on the left child node  
Else
  If a right child node does not exist
    Create a new BinarySearchTree with the new value and updated depth and assign it to the right pointer
  Else
    Recursively call .insert() on the right child node

Let’s illustrate the insertion procedure with a tree whose root node has the data 100. At each step, an arrow will point at the node being processed.

Insert 50
50 < 100, left child node doesn't exist, create a left child node with value 50 and depth 2

    ==> 100
       /
      50

Insert 125
125 > 100, right child node doesn't exist, create a right child node with value 125 and depth 2

    ==> 100
       /   \
      50    125

Insert 75
75 < 100, left child node with value 50 exists, recursively insert at left child

    ==> 100
       /   \
      50    125

75 > 50, right child node doesn't exist, create a right child node with value 75 and depth 3

        100
       /   \
  ==> 50    125
       \
       75

Insert 25
25 < 100, left child node with value 50 exists, recursively insert at left child

    ==> 100
       /   \
      50    125
        \
        75

25 < 50, left child node doesn't exist, create a left child node with value 25 and depth 3

        100
       /   \
  ==> 50    125
     /  \
    25  75

Note that we need to update the depth of each inserted node. To do so, we add 1 to the current node’s depth when we insert a node as a left or right child.

Let’s implement this .insert() method!

Instructions

1.

Define a method, .insert(), with the parameters self and value, below the constructor method.

The method is not doing anything yet, so fill it with a pass statement.

2.

We want to know where to place the target value. If the target value is less than the root node’s value, we will need to place it in the left child node. Before doing so, we need to check if the left child node does not exist. If it does not exist, we will add another level to our Binary Search Tree by creating a left BinarySearchTree with the target value and a depth one more than the root node. If the left child node does exist, we will recursively call the .insert() method for the left child node.

Remove the pass statement inside the .insert() method, and write an if statement that checks if the target value is less than the root node’s value. If so, we want to place this on the left side of the tree.

  • Nest an if statement that checks if a left child node does not exist (or is None). If it does not exist, instantiate a BinarySearchTree with the target value and a depth one greater than self.depth, and assign it to self.left.
  • Right after this if block, add an else block, also nested in the outer if. This else code executes if a left child already exists. Inside the else, call the .insert() method for the left child node passing the target value as the argument.
3.

Alternatively, if the target value is not less than the root node’s value, we will place it in the right child node. Before doing so, we need to check if a right child node does not exist. If no right child node exists, we will add another level to our Binary Search Tree by creating a right BinarySearchTree with the target value and a depth one more than the root node. If it does exist, we will call the .insert() method of the right child node.

  • Create an else statement block parallel to the outer if statement from the previous step.
  • Nest an if statement that checks if a right child node does not exist. If it does not exist, instantiate a BinarySearchTree with the target value and a new depth and assign it to self.right.
  • Right after this nested if, add an else statement such that if right does exist, call its .insert() method passing on value.
4.

Let’s add some print statements in .insert() so we can verify the value is added correctly according to the rules of the Binary Search Tree!

Inside .insert():

  • Just after you create a new BinarySearchTree on the left of the node, in the next line paste this print statement:

    print(f'Tree node {value} added to the left of {self.value} at depth {self.depth + 1}')
  • Just after you create a new BinarySearchTree on the right, in the next line paste this print statement:

    print(f'Tree node {value} added to the right of {self.value} at depth {self.depth + 1}')
5.

A BinarySearchTree has been created for you with an initial value of 100. Insert the following values to the tree in this order:

  • 50
  • 125
  • 75
  • 25

At each step, verify the output and make sure the nodes insertion messages match their intended position:

100 / \ 50 125 / \ 25 75

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?