Number of leaf nodes in a binary tree

I have read that the number of leaf nodes in a tree of height h is at least h+1

But as shown here in the pic

the tree is of height 2 开发者_StackOverflow中文版but the number of leaf nodes is just 2 (at least) and not 3. Where am I mistaken?

The statement you made is true if and only if you're talking about a perfect binary tree:

A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level

The statement that the number of leaves in a tree of height h is at least h + 1 is patently false - just consider a linked list of length h, which has only one leaf node. Either the source you read is incorrect, or it was making some extra assumptions about the structure of the tree.

EDIT: It's possible that the original proof said that there are at least h + 1 NULL pointers in the tree. This statement is indeed true, as we can see by induction. As a base case, the single node tree has height 0 and has two NULL pointers, so the claim holds for h = 0. For the inductive step, assume the claim holds for all trees of height h' < h and consider any tree of height h. One of its subtrees must have height h - 1 and by the inductive hypothesis must have h NULL pointers. Now consider the other subtree. If there is no other subtree, the root contributes the (h + 1)st NULL pointer and we're done. Otherwise, there is a subtree of height k for k ≥ 0, and so by the inductive hypothesis there are at least (k + 1) ≥ 1 NULL pointers, so the tree itself has at least h + 1 NULL pointers, completing the proof.

I know this is old, but in case anyone else comes across here, to find the leaves: (n - 1) - ( n / 2) where n = the total number of nodes. In this case that is (4 - 1) - ( 4 / 2) = 3 - 2 = 1