UGC NET CSE | December 2007 | Part 2 | Question: 23

Question

The height of a binary tree with $n$ nodes, in the worst case is :

• A. $O(log n)$
• B. $O(n)$
• C. $\Omega(n\log n)$
• D. $\Omega(n^2)$

Answer 1

In the worst case a binary tree can be either

1. Right Skewed, or

2. Left Skewed.

in either case, the tree is a straight line or TOSET like structure.

Thus making the height equal to the number of nodes in the tree i.e. O(n). Hence, B is the correct option.

Also making the search sequential with O(n) running time.

To mitigate this problem AVL Tree uses the concept of BALANCE FACTOR. Therefore AVL Tree guarantees O(log n) search time.