FlowerFire
FlowerFire

Reputation: 81

Height range of binary tree

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

Answers (2)

ChuckCottrill
ChuckCottrill

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

sam092
sam092

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

Related Questions