Question

Arrange the following binary tree types in increasing order of height with the worst-case height of each type.

Binary Tree

Full Binary Tree

Complete Binary Tree

Binary Search Tree

Balanced Binary Tree

Answer 1

In case of Binary tree and Binary Search Tree, the worst casee happens when every node has a single children, thus with n nodes then height becomes O(n), and they have the largest height possible. Still a Binary Search Tree can manage to have an upper bound of O(n) in cases where some nodes can be having two children. So largest height is of Binary trees then Binary Search Trees.

In a balanced binary tree, the difference between heights of any two leaves can not be greater than 1. It's height in worst case is also O(n/2), which is O(n).

In full binary tree, every node is bound to have two children except leaves. It can have any height between ordern of log(n) and O(n). In worst case,, the height is O(n/2), which is O(n).

A complete binary tree is a full binary tree with constrint of having every level completely filled except last, making it's worst case O(log(n)).

Keeping all these points in mind, the order of worst case heights is:

Complete Binary Tree < Full Binary Tree = Balanced Binary Tree < Binary Seach Tree < Binary Tree.

Please ask any doubts in comments.