You are here:

Advertisement

Please explain “In a binary tree of n nodes there are n+1 null pointers representing children”

Dear Mala:

When you have n binary tree nodes, you know that each node has two child nodes. You also know that they are each connect to one and only one other node node directly. n nodes that are connected together must have n-1 connections. Thus n-1 child nodes are used because nodes are only connected to other nodes via child nodes. So to sum it all up, there are:

2n - (n-1) = n + 1 child nodes that are not used and are represented by null pointers since they do not point to other nodes.

Again, 2n is the total number of child nodes and n-1 is the total number of child nodes that are each connected to only one other node.

C , MFC, Object Oriented, Artificial Intelligence

I have over ten years experience in the field of Computer Science, five years experience developing C/C++. I recently wrote a chess program using Object Oriented, C++, MFC.**Education/Credentials**

Master's Degree Computer Science from Johns Hopkins