You have now completed the necessary steps to represent a BTree in Python and can now move on to implementing the fundamental operations needed to leverage BTrees. We start first with an insert method. Insert has multiple steps in the general implementation, but we will first start with inserting values into nodes. First, we fill a BTree. We will only need to fill in the keys of the root element until it’s full. More specifically:

- When we insert a new value, we first check if the root has space.
- If so, and the root is a leaf, we can insert the value into the root.
- To insert a value into a node, we need to make sure the keys stay in order, and thus we insert in order (don’t append and then sort).

For testing, we will set a high branching factor in this exercise, so all values are inserted into the root node. Here and in the coming exercises, we will split our implementation between the `BTreeNode`

and `BTree`

classes, so be aware of what is going where when implementing.

### Instructions

**1.**

Start by implementing the `add_key()`

method in `BTreeNode`

, which takes in a `value`

argument. Here, we need to make sure that when adding keys, they stay in ascending order.

To do this, our code will be as follows:

- Iterate over the length of
`self.keys`

. - Check if
`value`

is less than the element in`self.keys`

we are at. - If
`value`

is less than the element, insert`value`

at the index of the element. - If this condition isn’t hit during the iteration, append
`value`

at the end of`self.keys`

.

**2.**

Next, implement the initial `insert()`

method in `BTree`

. This function will be added too later, but for now, take in a value and add it to the root node using the root node’s `add_key()`

method.

Click the hint if you feel stuck.