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

1
votes

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?

1
algorithmdata-structurestreebig-o
Maybe cs.stackexchange.com would be a better place for your question – Rod
It's not really DFS (or BFS) when searching an ordered tree. The "F" stands for "First", implying there's at least one other option, but there's no choices to be made with ordered trees. You know exactly the path to take. – ikegami
Right. For an ordered tree (balanced or not), you'd use: n = root; while (n) { if (n.value == target) return n; n = n.value < target ? n.left : n.right; } return NULL;. No need for a stack (DFS) or queue (BFS) for backtracking since there's no backtracking. – ikegami
Balancing the tree limits the maximum depth of the tree, which limits the maximum number of iterations of the while loop. – ikegami
No, there's no backtracking with ordered trees. It's O(log N) for balanced and O(N) for unbalanced (since you could effectively have a linked list). With unordered trees, you have to visit every node, so it's O(N). The depth of the tree has no effect on the number of nodes to visit, so balancing doesn't help. – ikegami

1 Answers

5
votes

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.