CS 70

BST Insert

  • LHS Cow speaking

    Now let's imagine adding new keys to our tree.

Imagine we are going to insert the key 47. Where should it go?

When we insert 47, what key will the new node's parent have?

INSERT Pseudocode

At a high level, to insert a key we just use our look-up procedure to find the spot for the new node, then place it there.

Let's make some pseudocode to make it precise!

Trees have a naturally recursive structure—trees are made of trees. So it makes sense to write insert recursively!

  • Hedgehog speaking

    Oooh. I don't…really like recursion…

  • LHS Cow speaking

    We know it takes some time to get comfortable with recursive algorithms, but it's a really useful way of thinking.

  • RHS Cow speaking

    That's why it's so important to practice!

Designing Recursive Algorithms

Here are the main steps to designing a recursive algorithm:

  1. Identify precisely what the algorithm will do.
    • What inputs does it take?
    • What results does it promise?
  2. Identify the base case.
    • What is the simplest possible input?
    • How do we satisfy the promise in that case?
  3. Identify the recursive step. (This is the part that trips a lot of people up!)
    • We know what our algorithm does, right?
      • We decided in Step 1.
    • So let's assume that it really works, but only for inputs “closer” to the base case than the one we have.
    • We carve off a smaller chunk of our problem and use our algorithm on it, relying on the promise we made.
    • Then we take that result and do whatever else we need to do to satisfy the promise for the input we were given.
  4. Double check: Does our algorithm actually satisfy the promise?
    • If not, go back to Step 1 and iterate on the design.

Step 1: BST-INSERT Specification

So let's say that our algorithm BST-INSERT takes a BST, tree, and an item to insert, x.

Let's say that BST-INSERT(tree, x) promises that, when it returns, tree will contain x and that tree will still be a valid BST.

(For now, to keep things simple, we will just assume that x is not already in the tree; we can handle x already being in the tree pretty simply in our implementation.)

Step 2: Base Case

What is the simplest possible tree and how would one insert x into that tree?

The simplest possible tree is the tree with no nodes at all: the empty tree!

Inserting a node into the empty tree is easy: just make the node the root. Done!

Step 3: Recursive Step

The main thing here is that we assume that we already have a function BST-INSERT that does exactly what we promised! It takes a BST and an item and inserts that item into the tree, leaving it a valid BST. The only catch is that we need to user our function on smaller trees than the one we have.

So what smaller tree should we insert x into in order to fulfill our promise?

A tree that isn't empty has a node and then a left and right subtree. So, these subtrees will clearly be smaller trees that we can recurse on.

Which one to choose depends on how x compares to the root of our tree. We need to ensure that tree is a valid BST after x is inserted.

In order to maintain that property, we must insert x into the left subtree if it is less than the key at the root, and into the right subtree if it is not.

  • Horse speaking

    Hay! What if the key is equal to the root?

  • LHS Cow speaking

    For simplicity, we'll assume for now that the key is not already in the tree, so that case doesn't come up.

Final Pseudocode

Here's the algorithm we've just developed:

BST-INSERT(treenode, x):
    if there isn't a treenode (i.e., this subtree is empty):    // base case
        replace empty subtree with new tree node containing x as its value (and empty subtrees)
    else if x < treenode.value:
        BST-INSERT(treenode.leftSubtree, x)        // recurse on smaller case (left subtree)
    else:    // x >= treenode.value
        BST-INSERT(treenode.rightSubtree, x)     // recurse on smaller case (right subtree)

Insert Practice

Choose one of the following sequences of keys, and insert the keys into a tree (starting from empty) in that order.

D, B, A, F, E, C, G

D, F, E, G, B, A, C

D, B, C, A, F, G, E

D, F, B, G, A, E, C

D, B, F, C, A, G, E

D, F, B, G, C, A, E

D, F, G, B, A, C, E

D, F, B, A, G, E, C

D, F, E, G, B, C, A

D, F, B, C, E, G, A

D, F, B, E, A, C, G

D, B, F, A, E, G, C

D, B, F, G, E, A, C

D, B, C, F, A, E, G

D, F, B, G, E, A, C

D, F, B, A, C, E, G

D, B, A, C, F, G, E

D, B, F, E, A, C, G

D, F, G, E, B, C, A

D, B, F, A, E, C, G

D, B, C, F, G, A, E

D, F, B, A, E, C, G

D, B, F, E, A, G, C

D, F, B, C, G, E, A

D, B, F, A, G, E, C

D, B, A, F, G, E, C

D, B, A, F, C, G, E

D, G, E, B, G, A, C

D, F, E, B, C, A, G

D, F, B, E, C, A, G

D, B, A, F, C, E, G

D, B, F, E, C, G, A

D, B, F, C, G, A, E

D, B, C, F, E, G, A

D, B, F, C, E, G, A

D, B, F, C, E, A, G

D, F, G, B, C, E, A

D, B, F, G, E, C, A

D, B, C, F, G, E, A

D, F, B, E, A, G, C

D, F, B, C, G, A, E

D, F, B, E, G, C, A

D, B, F, A, C, G, E

D, F, B, G, C, E, A

D, F, B, E, C, G, A

D, F, E, B, A, G, C

D, F, B, A, C, G, E

D, F, G, C, A, G, E

D, F, E, B, C, G, A

D, B, F, G, C, A, E

D, F, B, G, E, C, A

D, F, B, C, A, E, G

D, B, C, F, E, A, G

D, B, F, C, G, E, A

D, F, G, B, A, E, C

D, B, F, A, G, C, E

D, B, F, G, A, C, E

D, F, G, E, B, A, C

D, F, G, B, C, A, E

D, B, A, F, G, C, E

D, B, F, A, C, E, G

D, F, E, B, A, C, G

D, F, E, B, G, C, A

D, B, F, E, G, A, C

D, F, B, A, E, G, C

D, B, F, G, C, E, A

D, F, B, A, G, C, E

D, F, G, B, E, C, A

Did you draw the tree?

Here is what the tree should look like:

  • Duck speaking

    Wait, what? How did you know which sequence I picked?

  • LHS Cow speaking

    I didn't! All of those sequences actually generate the same tree!

More Insert Practice

Starting from an empty tree, insert the following sequence: A, B, C, D, E, F, G.

Did you draw the tree?

Here is the tree you just built:

What is notable about the two trees we've just built? (i.e., compare and contrast them)

These are the shortest and tallest possible trees, respectively!

  • The first one is a perfectly balanced tree. For any node, the left and right subtrees have exactly the same height.
    • Its height is \( \Theta( \log{n} ) \).
  • The second one is what we call a "stick." It is essentially a linked list.
    • Its height is \( \Theta( n ) \), where \( n \) is the number of nodes.

So we see that the height of the tree depends a great deal on the order in which keys are added.

  • Rabbit speaking

    There's something else that's interesting. There are lots of ways to build a perfectly balanced tree, but only one way to build this particular stick.

  • Dog speaking

    But there ways to build other sticks! For example, we could have inserted the keys in the order G, F, E, D, C, B, A. I wonder how many different sticks there are?

  • LHS Cow speaking

    You could actually figure that out if you like... It's not too hard.

(When logged in, completion status appears here.)