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

Hi, Mala.

This is just a stated observation about a property of binary trees.  I assume you are familiar with the concept of a binary tree (if not, please let me know in a followup and I'll go over binary tress, too, since this next part may not make too much sense without basic knowledge of binary trees).

Consider a single-node binary tree.  This is just a root node:

  /    \

Notice that there is one node, and two NULL child nodes.  Let's assume that we add one more element to this tree:

      /    \
  /    \

Notice now that there are two nodes and three NULL child nodes.  For every node you add, you remove one NULL child node (because the new node takes its place) and add two new NULL child nodes (because the new node has two NULL child nodes).  So for any binary tree of n nodes, you always have n + 1 NULL child nodes.  It's just an observed property of a binary tree stated in a generic form.

I hope that clears things up for you.  If you have further questions, please let me know.  I'm here to help. :)


All Answers

Answers by Expert:

Ask Experts


Joseph Moore


I've been programming in one form or another since my brother taught me BASIC when I was 6. I've been programing professionally since I was 20, first web development with HTML, JS, DHTML, CSS, etc., then I became a video game developer, writing code in C, C++, C#, SQL, assembly, and various scripting languages. I've even written my own scripting languages, custom designed for the games I was making. I also dabble in Java, PHP, and Perl. I've worked on pretty much every aspect of game development, including graphics, audio, gameplay, tool, UI, input, animation, and physics.


I've been writing C++ code for 12 years, both on my own in my spare time and professionally.


Bachelor of Science in Game Design and Development, Full Sail University, Winter Park, FL

Awards and Honors
Salutatorian and Advanced Achiever Awards at Full Sail; Independent Games Festival Student Showcase winner, 2004; Featured article on Gamasutra about an experimental game developed in 2004

©2016 About.com. All rights reserved.