CODEWITHSUNDEEP
algorithmdata-structuresbinary-tree
ApplePieIsGood
ApplePieIsGood

Reputation: 3731

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

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);
 }

Upvotes: 1

Views: 2083

Answers (5)

paxdiablo
paxdiablo

Reputation: 881223

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).

Upvotes: 1

Kekoa
Kekoa

Reputation: 28240

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).

Upvotes: 0

JP Alioto
JP Alioto

Reputation: 45117

Some good info in this SO answer.

Upvotes: 0

Pesto
Pesto

Reputation: 23880

Yes, which is why self-balancing BSTs exist.

Upvotes: 0

Pete
Pete

Reputation: 18075

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 .

Upvotes: 0

Related Questions