1 node appearing less in recursive implementation of Tree in C++

Question

I have created an implementation of a complete binary-tree in C++ using class and recursion. At depth = 6 it is supposed to have 63 nodes. But in the output I can see only 62 nodes. Can someone please point out the problem?

class node{
public:
 node *left, *right, *root, *it;
 int data,m;
void create(){
 root = new node;
 it = root;
 root->data = 1;
 const int n = 6; // Depth to be passed 
 addchildren(root,n); }
void addchildren(node *x,int z) // Recursion (z = No. of levels)
 {
 if (z==1)
 return;
 else
 {
 it->left = new node;
 it->left->data = 1;
 it->right = new node;
 it->right->data = 1;
 addchildren(it->left,z-1);
 addchildren(it->right,z-1);
 return;
 }
 }
void display(node *x,int z) 
 {
 if (z==1)
 return;
 else
 {
 cout<<it->left->data;
 cout<<it->right->data;
 display(it->left,z-1);
 display(it->right,z-1);
 return;
 }
 }
};
int main()
{
 node A;
 A.create();
 A.display(A.root,6);
}

Output : 11111111111111111111111111111111111111111111111111111111111111 (62 1s)

• PaulMcKenzie: How to debug small programs

Answer 1

Take a look at your display function:

void display(node *x,int z) {
 if (z==1)
 return;
 else
 {
 cout<<it->left->data;
 cout<<it->right->data;
 display(it->left,z-1);
 display(it->right,z-1);
 return;
 }
 }
};

Let's Rubber Ducky this function:

If we're on the lowest row of the tree, just return instead of displaying it.

Else, display out two children on the row below us, and then have them display their children.

This is an...interesting way of writing a display for a tree. I'd strongly suggest just printing the node you're currently on and then letting its children print themselves. This convoluted way of printing children yourself is causing your problem. After all, who is the root node a child of? Nobody! So who prints the root node? Nobody!!

In addition to this, you really really really need to set the left and right pointers in your nodes. As of now you have a bunch of wild pointers. I'd suggest adding a constructor to your node class to do this for you.

And lastly: why are you testing with a depth of 6? If I had to count that many 1's every time I ran the program to test I'm pretty sure I'd be pulling my hair out in the space of an hour. Start with a tree of depth 1 (which should fail with your current code!). If that works, go to a depth of 2. At most I'd test with a depth of 3. After all, the case of depth 6 vs. 3 is probably not at all different!

• Sirius Black: Thank you for the very detailed answer sir. I didn't get the part about wild left and right pointers. Are you talking about the last level of nodes?
• scohe001: @SiriusBlack See the Wikipedia article on Wild Pointers for more. Essentially, uninitialized pointers cause UB which is baaaaaad. I'd also suggest looking at some implementations of a BST print to see how they do it without passing in depth.