271 views

I am geting confused with the term maximum of p sons , otherwise I was applying handshaking lemma but this maximum word is where I am getting stucked , so plz clarify this .

maximum of $p$ sons means a node can have maximum $p$ children and therefore $p$ pointer fields are allocated in each node. Now total number of nodes is $q$, so total number of fields allocated is $pq$. Every node in the tree must be pointed by its parent (except root), so $q - 1$ fields must point to some node. So fields which are NULL = $pq - (q - 1) = q(p-1)+1$

You said q-1 fields must point to some node , what about leaf nodes .

Also leaf nodes won't be having children so then what about them ?

What does each field contain? A pointer to a child. Which nodes are children of some node? Every node except root. So there will be exactly q-1 non null fields which point to all nodes except root. Leaves will also be contained in these q-1 nodes, they are not special.

1 vote