In binary tree there are
n ancestor at level n.
Proof :
Take P(0): At node level
0, it has no ancestors since this is a roo tnode.
Take P(1): At node level
1, it has one ancestor. The ancestor is the root, its parents which is at level
0.
Take P(K): A node level
K it has K ancestors. Its parent is at level K – 1.
Take P(K+1): At node K +
1 level have more than one ancestor than that of node at k level.
Thus there are n ancestor
at level n in binary tree.
