You are here:

# C++/sir

Question
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++

Volunteer

#### Titus B. Ledbetter, Jr.

##### Expertise

C , MFC, Object Oriented, Artificial Intelligence

##### Experience

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