Learn

Inserting into a splay tree is similar to inserting into a regular binary search tree. First, we need to identify the correct location in the tree to add the new node. Once the new node is inserted, we splay that node to make it the root.

Let’s implement this logic in Python.

### Instructions

**1.**

We have laid out the following starter code in `insert()`

:

new_node = Node(value) current_node = self.root if current_node is None: self.root = new_node return last_parent = None while current_node is not None and current_node.value != new_node.value: last_parent = current_node break # Checkpoint 1 # Checkpoint 2 new_node.parent = last_parent

Within the while loop, implement the following logic:

- If the value of the new node is less than or equal to the value of the current node, set the current node to the next node on the left (traverse to the left).
- Otherwise, set the current node to the next node on the right (traverse to the right).

Make sure to delete the `break`

statement.

**2.**

Below `new_node.parent = last_parent`

, implement the following logic:

- If the value of the new node is less than the value of the last parent, set
`last_parent.left`

equal to`new_node`

. - If the value of the new node is greater than the value of the last parent, set
`last_parent.right`

equal to`new_node`

.

After this, splay the new node to make it the root.

# Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.