When inserting to a BST, is the first item inserted always the root of the tree?

Question

Looking at the implementation on Wikipedia, it would seem that a standard BST (non self balancing) never re-arranges itself during inserts, and so the very first item added will always be the root. Is this correct? If so, doesn't that mean that there is the potential for a BST to often have much worse than O(logN)?

Using this as a reference for a recursive insert:

 /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

Answer 1

Yes, the order of insertion can have negative effects on the shape/balance of the resulting tree. As you pointed out, the resulting worst case for a tree is worse than O(log(N)) and could end up looking simply like a linked-list .

Answer 2

Yes, which is why self-balancing BSTs exist.

Answer 3

Some good info in this SO answer.

Answer 4

Yes, unbalanced BSTs can be bad. In fact if you add sorted data to a BST, you can quickly degenerate your tree to single linked list performance, which has an insert of O(n), assuming an insert is at the end.

A standard BST will do decently well on average if you are dealing with random data. You're worst enemy is sorted, or reverse sorted data.

This is why you'll usually want to use a balanced BST(just pick one from your language's library).

Answer 5

Yes, it will always be on the root node simply because:

• that's the only place you can put it in an empty tree; and
• you're not moving it.

Of course, you can delete it which will result in another node becoming the root but that doesn't move the original first node elsewhere in the tree.

The degenerate case for an unbalanced binary tree is a linked list, which has a search time complexity of O(n).