How is a list of elements added to the binary search tree diagram?

Question

I found a lot of source codes on how to add element to a binary search tree, but I wasn't able to find illustration of adding an element to a binary search tree in a diagram form.

For example if I was given: {55, 34, 54, 2, 78, 12, 9}

Can you please show me step-by-step how it's added to the BST?

               x

         b            y
      v     g      h     t

Like the tree diagram above. (It's just a tree example not sorted or anything)

Answer 1

This is a simple implementation (i.e not considering rebalancing the tree).

{34, 54, 2, 78, 12, 9}


         55 <-- root

You take the next element and compare it to the root. If it's greater, you add it to the right, otherwise to the left.

{54, 2, 78, 12, 9}


         55 <-- root
       /
     34

You do the same operation for the other elements recursively.

{2, 78, 12, 9}


         55 <-- root
       /
     34
       \
       54

---

{78, 12, 9}


          55 <-- root
        /
      34
     /  \
   2     54

---

{12, 9}


           55 <-- root
        /        \
      34         78
    /    \
   2      54

---

{9}


          55 <-- root
        /       \
     34         78
   /     \
  2      54
   \
    12

---

          55 <-- root
        /       \
     34         78
   /     \
  2      54
   \
    12
   /
  9

Let me know if something is unclear.