In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.

ROOT
L R
/ \ / \
/ \ / \
----- -----

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.

To solve this suppose that there is a almost complete binary tree (just for proving) ,tree will be having 1 more level on the left of it.

For eg.

Array :[1,3,2,4,5,6,7,8,9,10,11] just make the binary tree out of it, and you will be able to visualize it easily.

Now suppose you call Max-Heapify(Array,1) then you will be able to visualize from above example that every time the problem will get divided into a sub-problem of size 2n/3.Till we reach the leaves.

For Mathematical approach read below..

For a complete binary tree of height h, number of nodes is f(h) = 2^(h+1) - 1.--------------(a)

In above case we have nearly complete binary tree with bottom half full. We can visualize this as collection of root + left complete tree + right complete tree.

If height of original tree is h, then height of left is h - 1 and right is h - 2. So equation becomes

n = 1 + f(h-1) + f(h-2)-----------(1)

We want to solve above for f(h-1) expressed as in terms of n(using a)