Relationship between number of nodes and height

Question

I am reading The Algorithm Design Manual. The author states that the height of a tree is:

h = log n, 
where 
h is height 
n = number of leaf nodes
log is log to base d, where d is the maximum number of children allowed per node.

He then goes on to say that the height of a perfectly balanced binary search tree, would be:

h = log n

I wonder if n in this second statement denotes 'total number of leaf nodes' or 'total number of nodes'.

Which brings up a bigger question, is there a mathematical relationship between total number of nodes and the height of a perfectly balanced binary search tree?

Answer 1

sure, n = 2^h where h, n denote height of the tree and the number of its nodes, respectively.

proof sketch:

a perfectly balanced binary tree has

• an actual branching factor of 2 at each inner node.
• equal root path lengths for each leaf node.

about the leaf nodes in a perfectly balanced binary tree:

as the number of leafs is the number of nodes minus the number of nodes in a perfectly balanced binary tree with a height decremented by one, the number of leafs is half the number of all nodes (to be precise, half of n+1).

so h just varies by 1, which usually doesn't make any real difference in complexity considerations. that claim can be illustrated by remembering that it amounts to the same variations as defining the height of a single node tree as either 0 (standard) or 1 (unusual, but maybe handy in distinguishing it from an empty tree).

Answer 2

It doesn't really matter if you talk of all nodes or just leaf nodes: either is bound by above and below by the other multiplied by a constant factor. In a perfectly balanced binary tree the number of nodes on a full level is the number of all nodes in levels above plus one.