CODEWITHSUNDEEP
algorithmdata-structurestreebig-o
aarti
aarti

Reputation: 2865

Can there exist a balanced binary tree that is not a balanced binary search tree? What is the time complexity?

Can there exist a balanced binary tree that is not a balanced binary search tree? If so, what would the time complexity be to search a node in such a tree.

My understanding is this:

  1. Binary Tree: any node has two maximum leaf nodes. Searching in a binary tree, using DFS or BFS is O|V+E|
  2. Binary Search Tree: A BST is a tree of ordered nodes. Searching in a binary search tree, using DFS is O|log n|
  3. Balanced Tree(assuming height-balanced): Maximum number of levels below the root is kept to the minimum. Does being balanced have any effect to the time complexity of search?

So, essentially, can I create a binary tree that is height-balanced but not ordered. Would the search time of this tree be O|V+E| or will it be better?

Upvotes: 1

Views: 586

Answers (1)

ikegami
ikegami

Reputation: 385849

Searching an unordered binary tree requires visiting every node, so it's O(N) whether it's balanced

          50
       __/  \__
      /        \
    25          26
   /  \        /  \
 49    46    48    47

or not

          50
       __/  \__
      /        \
    25          26
   /  \
 49    46
      /  \
     5    6

There's really no point in balancing an unordered tree.

Upvotes: 5

Related Questions