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.


All Answers

Answers by Expert:

Ask Experts


Titus B. Ledbetter, Jr.


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.

Master's Degree Computer Science from Johns Hopkins

©2017 About.com. All rights reserved.

[an error occurred while processing this directive]