What is the time complexity of insertion,deletion and searching an element in binary tree and binary search tree?


#1

What is the time complexity of insertion,deletion and searching an element in binary tree and binary search tree ? please give the correct comparison ?


#2

for binary search tree :
Algorithm Average Worst Case
Space O(n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

see this doc http://bigocheatsheet.com/
for the time complexities in one place


#3

Binary Tress:

  1. insertion:O(n*n)
  2. Deletion:O(log n)
  3. Searching:
    Binary Search Tree:
  4. Insertion O(n)
  5. Deletion:O(n) for worst case.O(log n) for best case
  6. Searching:O(n)

#4

Insertion in BST is O(logn) in average and 0(n) in worst case.


#5

Average case for all the operations of BST is O(log n)
Worst case is O(n) where n is the height of the tree