CODEWITHSUNDEEP
algorithmtreebinary-treebinary-search-tree
JAN
JAN

Reputation: 21855

Is it possible to insert elements to BST with complexity lower than O(n) worst case?

Given the following algorithm for inserting elements into BST : 

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

This algorithm runs in O(n) worst case .

Is it possible to insert elements into a BST using an algorithm with a lower complexity then O(n) , in the worst case ?

Remark 1 : This is not homework (preparing for an upcoming exam)

Remark 2 : without using AVL trees

Thanks

Upvotes: 0

Views: 264

Answers (1)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

The insert is equivalent to a search operation. Clearly if your tree is not balanced, the worst-case will always be a tree in the form of a linked-list. So there is no way to avoid the O(n).

Upvotes: 6

Related Questions