Balanced Binary Tree Vs Balanced Binary Search Tree

Question

For each of these operations would a balanced binary search tree complete the task in a faster big oh time than a balanced binary tree?

1. Finding the smallest item in the tree.

I think balanced BST would have a faster big oh time than a balanced Binary Tree since you can just keep traversing left and find the smallest item. I think it would be O(log n).

2. Creating a list of all elements in the tree that are smaller than some value v.

For 2 could someone offer me an explanation about which one would have a faster big oh time?

Answer 1

You also have to take into account best, average and worst case scenarios in time complexity performance, keeping in mind what the value of n represents:

---

1. Balanced Binary Search Tree representation

           25             // Level 1
        20    36          // Level 2
      10 22  30 40        // Level 3
  .. .. .. .. .. .. .. 
.. .. .. .. .. .. .. ..   // Level n

---

2. Binary Search Tree representation

           10           // Level 1
          9  11         // Level 2
         8 . . 20       // Level 3
        7 . . 15 24   
       6 . . . . . . .  // Level n
         

Finding the smallest item in the tree.

This is a search operation.

1) The time complexity in here is O(log n), even in worst case scenario, because the tree is balanced. The minimum value is 10.

2) The time complexity here in the worst case scenario is O(n). The minimum value is 6. You can picture from the representation that the root's left tree (branch) behaves like a linked list. This is because the tree is unbalanced. [1]

Creating a list of all elements in the tree that are smaller than some value v.

This would be an insertion operation.

1) This would be O(log n), because as the tree is traversed it is balanced so you don't get 2)'s scenario.

2) This would be O(n), because in the worst case scenario your insertion will resemble insertion of a linked list.

In conclusion: A Balanced Binary Search Tree guarantees O(log n) in all cases of search, insertion and deletion of nodes, where as a typical BST does not.

---

Citations

Best, worst and average case [1]