Balanced Binary Tree Vs Balanced Binary Search Tree

4
votes

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

  1. 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?

2
algorithmtreebinary-treebig-obinary-search-tree
feel free for any queries. – Sumeet

2 Answers

5
votes

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
         7 . . 20       // Level 3
        8 . . . 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]

1
votes

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

Well, in Big O notation both balanced binary search tree and balanced binary tree would perform the same and time would be O(N), which is linear time complexity.

For the Balanced Binary Search tree, we would do an inorder traversal and keep adding all the keys to the list until we encounter the node with key v(inorder traversal of BST leads to ascending ordering of keys). Now worst case occurs when v is the largest key that is present in the BST, therefore, time complexity is O(N).

For a balanced binary tree, its as good as traversing the entire tree and adding all the keys to the list that are less than v. So time complexity here also is O(N).