C++/sir

Advertisement


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

Answer
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:

   NODE
  /    \
NULL    NULL

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

       NODE
      /    \
   NODE    NULL
  /    \
NULL    NULL

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. :)

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Joseph Moore

Expertise

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.

Experience

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

Organizations
IGDA

Education/Credentials
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.