CORMEN

Question

What is the asymptotic performance of TREE-INSERT when used to insert n
items with identical keys into an initially empty binary search tree?

Answer 1

In Binary Search Tree, if We encounter same value which a node present in the Tree then we can insert into either left side or right side, it's our choice...

 

let take it is left side...

 

We all know that in BST,

insertion takes = O(h) , ===> it leads to O(n)

Comments

got it, great explanation, thank you

---

Can we insert same values again and again because duplicate values are not allowed in a binary tree.

---

There is no rule that duplicates are not allowed....

generally we don't enter duplicates... but it can't be the always

Answer 2

The worst case complexity of TREE-INSERT in the case of the Binary Search Tree is O(n). So when we are inserting n keys then also it will be the same i.e. O(n)

We cannot insert duplicate keys in the Binary Search Tree. So if you are inserting n identical keys then only one key will be inserted and as the binary search tree is empty initially so O(1) for the first element. Rest of them wont be inserted in the bst.

Comments

how can we have time complexity as O(1) as we have to compare n values with the root node as we know values are duplicate how can the tree will know.

---

if the tree is initially created and we are just inserting a single value i.e. that is the only value and no root node, so the complexity for that element would be O(1). I think that the rest of the elements can't be added as the duplicate values are not allowed. If they are allowed then it would be O(n) as the tree would grow in only a particular direction based on the condition.

---

but what about the time for comparison...

---

for comparison it would be O(n).. the net time would be O(n) ... but only a single element will be inserted..

Answer 3

what i think it will depend upon the code. that we are using for the insertion of a node in BST. if you have a condition where you compare values of root with >= or <= operator with the child you can insert the node. but if u have < or > operators  u cannot insert it as the value wont be found.

in both cases time will be O(n) ,as you have to compare the value with the previous one n times in duplicate case.