Binary Tree Height

First there may be some difference as to how computer science calculates the height of a tree, versus the way height is determined in discrete mathematics (graph theory), this may be due to the existence of data at any one node (or vertice), while in mathematics, its a pure theory approach.

So maybe its best you clarify which one you need.

In discrete mathematics, trees are classified as m-ary trees, so a bin-ary tree is a 2-ary tree. Also at any given height, there can be at most 2^h = L (leaves). This is important to notice, since it confirms that the root is at height zero, hence 2^0 = 1 leaf…1 vertice…the root.

So given n vertices, the height of a tree is given by the formula n = 2^( h + 1 ) – 1

Since you are looking for h, you have to take the log2 of both sides of the formula n = 2^( h + 1 ) – 1

For a full binary tree, the max height is log2( n + 1 ) = log2( 2^( h + 1 ) ) this equals ceiling( log2( n + 1 ) – 1 ) = h

For a non-full binary tree, the max height = ( n – 1 ) therefore if you have n vertices, the root must be subtracted to get the max height, because of the previous formula above (2^h = L)

For min heights, extrapolate from the above rules.

Leave a Comment

tech