Reputation: 81
I can mathematically prove that the possible heights of a binary tree is:logN <= Height <=N-1(N is the number of nodes). However, how do I explain this answer by using just one or two sentences?
Upvotes: 2
Views: 330
Reputation: 4444
A perfectly balanced tree (non-leaf nodes have 2 children) has size N=2^n-1 nodes, log2(N)=n levels.
The degenerate case of a tree (every node has single child) is a list, size N has N levels.
Upvotes: 1
Reputation: 1335
Consider 2 cases when minimum height and maximum height happens.
Minimum height: When each non-leaf node has exactly two children
Maximum height: When each non-leaf node has exactly one child, i.e. linear
Upvotes: 4