Why do we need a Height-Balanced Binary Tree?
Let’s understand the need for a balanced binary tree through an example.
The above tree is a binary search tree and also a height-balanced tree.
Suppose we want to find the value 79 in the above tree. First, we compare the value of the root node. Since the value of 79 is greater than 35, we move to its right child, i.e., 48. Since the value 79 is greater than 48, so we move to the right child of 48. The value of the right child of node 48 is 79. The number of hops required to search the element 79 is 2.
Similarly, any element can be found with at most 2 jumps because the height of the tree is 2.
So it can be seen that any value in a balanced binary tree can be searched in O(logN) time where N is the number of nodes in the tree. But if the tree is not height-balanced then in the worst case, a search operation can take O(N) time.