We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you a podcast all about Citrix Workspace, moving to the cloud, and analytics & intelligence. Episode 2 coming soon!Listen Now

x

# Binary tree in C++ - Counting the nodes in a tree

on
Medium Priority
3,501 Views
Background: Implement binary trees: creating tree nodes, growing a tree by attaching trees to a node, counting the nodes of a tree.

Problem: I've having trouble trying to code the btree.cpp, with the 4 functions. It's my assignment and i'm stuck with these codes.

Can anyone be kind enough to help me out with the 4 functions in btree.cpp?

``````
================== btree.h ================================
class Node {

private:
int key;
Node *l, *r;

public:
Node(int); // construct a Node with a given key
void attL(Node *); // take the given Node as left subtree
void attR(Node *); // take the given Node as right subtree
int count(); // return the number of nodes in the tree
};
==================================================

=================== btree.cpp ===============================
#include "btree.h"

Node::Node(int k) {
// create a tree node

key = k;
}

void Node::attL(Node *tree) {
// make tree the left sub-tree

attL(tree->l);
}

void Node::attR(Node *tree) {
// make tree the right sub-tree

attR(tree->r);
}

int Node::count() {
// return the number of nodes of the tree

int count = 1;   // Start by counting the root.

//return count;
}

==================================================

================== test.cpp ================================
#include <iostream>
using namespace std;
#include "btree.h"

int main() {
Node n1=1, n2=2, n3=3, n4=4, n5(5), n6(6), n7(7), n8(8);

cout << "n8\t" << n8.count() << endl;

n7.attR(&n8);
cout << "n7\t" << n7.count() << endl;

n4.attL(&n6);
n4.attR(&n7);
cout << "n4\t" << n4.count() << endl;

n3.attL(&n4);
n3.attR(&n5);
cout << "n3\t" << n3.count() << endl;

n1.attL(&n2);
n1.attR(&n3);
cout << "n1\t" << n1.count() << endl;
}
=======================================
i should be looking at this output:

n8 1
n7 2
n4 4
n3 6
n1 8
``````
Comment
Watch Question

## View Solutions Only

CERTIFIED EXPERT
Top Expert 2009

Commented:
>> void Node::attL(Node *tree) {
>>         // make tree the left sub-tree
>>
>>         attL(tree->l);
>> }

attL means : attach the Node passed as parameter to the current node (this), as the left sub-tree.

So, don't call attL recursively, but rather assign tree to the left sub-tree in the node.

Same for attR.

>> int Node::count() {
>>         // return the number of nodes of the tree
>>
>>         int count = 1;   // Start by counting the root.
>>
>>         //counting the nodes and adding.
>>        //return count;
>> }

You'll need to traverse the tree, starting from the current node as the root. Count all nodes that you encounter, and return the total count at the end.

Commented:
Hi Infinity08,

Thanks for your help! Correct me if i'm wrong, should it be this instead for the attL and attR:

void Node::attL(Node *tree) {
// make tree the left sub-tree

l = tree;      // this is the correct way?
//tree->l;      // or this?
}

For the counting, i'm not sure how to do the traversing. I managed to source some online help and what i got was something like this:

int size(struct node* node) {
if (node==NULL) {
return(0);
} else {
return(size(node->left) + 1 + size(node->right));
}
}

There's a parameter in this case, so i'm not sure how to get the count. Or should i be even looking at size?

Commented:
Anyone able to help me out?
CERTIFIED EXPERT
Top Expert 2009

Commented:
>> Correct me if i'm wrong, should it be this instead for the attL and attR:

Yes, looks good :)

Btw, in your constructor, you might want to initialize the left and right sub-trees to NULL to show that no sub-trees are attached to it (yet).

>> i got was something like this:

Do you understand how that code works ?

Try to think about it. If you have a tree, how would you count its nodes in your head, if you started at the root ?

Commented:
Thanks for the guidance.

Hmm, i'm still very unsure about the counting. Putting aside coding, if i will to count the nodes, i will probably start from the root and go either right or left first.

Say, count=1 with root, if there's no left, then right, count+1, then repeat again?

If put into programming terms, i have to have quite a number of loops? Or is there a way i do the checking of total left and total right sub-trees from the root.

For this coding, it's sum of the size of all the left subtrees with all the right subtrees and adding 1 which is the root. Am i right?

int size(struct node* node) {
if (node==NULL) {
return(0);
} else {
return(size(node->left) + 1 + size(node->right));
}
}

Are you able to guide me with some skeletons coding? Thanks a million.
CERTIFIED EXPERT
Top Expert 2009

Commented:
>> if i will to count the nodes, i will probably start from the root and go either right or left first.

Right, so say you go left first. Once you have counted all nodes on the left side, you go to the right, and count all nodes there. So, you get :

count(tree) = count(left sub-tree) + 1 + count(right sub-tree)

That is the so-called recursive approach to counting nodes in a tree (recursive because for counting the nodes in the left and right sub-trees, you call the same count method).

>> For this coding, it's sum of the size of all the left subtrees with all the right subtrees and adding 1 which is the root. Am i right?

Correct.

>> Are you able to guide me with some skeletons coding?

Well, now you understand how it's done, it should be relatively easy to put it into code. You have this method :

int Node::count() {
// ...
}

which has to count all nodes in the tree starting from the current node (this). So, you have 1 for the current node, and two recursive calls for the left and right sub-trees.

Commented:
I'm able to understand this:

count(tree) = count(left sub-tree) + 1 + count(right sub-tree)

as a pseudocode, but i'm rather lost when the method i have is just count() which doesn't parse in any parameter. In this case, how can do my count for my left and right subtrees?

Sorry i'm not able to see it in C++ context. =(
CERTIFIED EXPERT
Top Expert 2009

Commented:
The thing is that we're dealing with a method (member function). Methods have a hidden parameter, that is the object the method is called from.

So, if you call :

Node n;
int cnt = n.count();

then you call the count method for the n object. And the count method will count all nodes that are part of the tree with n as the root.

Commented:
Sorry that i'm not getting your point. =(

How close am i with this?

int Node::count() {
// return the number of nodes of the tree

return (1+ l.count() + r.count()) ;  // Return the total.
}
CERTIFIED EXPERT
Top Expert 2009
Commented:
>> How close am i with this?

Pretty close ;)

Except for two small things :

1) l and r are pointers to Node, so you need to dereference the pointer first before calling the method. ie. l->count() instead of l.count()

2) you need to account for the tree leaves (end points of the branches). At a leaf, the l (or r) pointer is NULL. If it is NULL, then the count for that sub-tree is obviously 0, and you cannot dereference the pointer. So, check for NULL before dereferencing the pointer.

Not the solution you were looking for? Getting a personalized solution is easy.

Commented:
You're a good teacher.

Here's my changes:

int Node::count() {
// return the number of nodes of the tree

int leftCount=0;
int rightCount=0;

if(l!=NULL)  // has left-subtrees
leftCount = l->count();

if(r!=NULL)  // has right-subtrees
rightCount = r->count();

return (leftCount + 1 + rightCount) ;  // Return the total.

}

Have i got it?
CERTIFIED EXPERT
Top Expert 2009

Commented:
>> Have i got it?

That should do the trick, yes :)

Now, try it with the test code, and see if you get the correct output. If there's anything still wrong, then you can post the whole code here again, and I'll have a look at it.

Commented:
Yes, it works! =)

I've some questions though. Hope you are able to answer my doubts:

1. The int variable key. What is the purpose of it? Sort of an identifier to the root node?

2. An alternative to l->count() is (*l).count()?

3. I'm not sure with the Nodes declared in test.cpp: (Node n1=1, n2=2, n3=3, n4=4, n5(5), n6(6), n7(7), n8(8)). Can you explain the difference with n1=1 and n5(5)?

4. How are the nodes counted in the test.cpp? The tree keep getting extended down the coding?

8
8
6           7
4           5
2         3

Is this correct?
CERTIFIED EXPERT
Top Expert 2009
Commented:
>> Hope you are able to answer my doubts:

Sure.

>> 1. The int variable key. What is the purpose of it? Sort of an identifier to the root node?

It is supposed to be the content of the node (there wouldn't be much point to the tree if nothing was stored in it). Here, for demonstration purposes, an int value is used, and each node has a different value, so it's easy to distinguish them.

>> 2. An alternative to l->count() is (*l).count()?

Correct. They do the exact same thing.

>> 3. I'm not sure with the Nodes declared in test.cpp: (Node n1=1, n2=2, n3=3, n4=4, n5(5), n6(6), n7(7), n8(8)). Can you explain the difference with n1=1 and n5(5)?

In this case, there is no difference in behavior. Both notations will call the constructor (that takes a single int as parameter), and construct a Node object.

They are semantically different though. n1=1 basically casts the int value 1 to a Node object (by calling the constructor). n5(5) explicitly calls the constructor.

I prefer the latter, as it's clearer what happens. A cast does not make a lot of sense (how do you cast an int to a Node - they're two different concepts - it's like saying that you transform a chair into a cupboard).

>> 4. How are the nodes counted in the test.cpp? The tree keep getting extended down the coding?

The recursive approach performs a depth-first search :

http://en.wikipedia.org/wiki/Depth-first_search

Note that the contents of the tree at the end of main look like this :

1
/ \
2   3
/  \
4    5
/ \
6  7
\
8

The depth first search would traverse the nodes in this order :

1 2 1 3 4 6 4 7 8 7 4 3 5 3 1

Or the total count would be :

(1) + 1 + (((1) + 1 + ((0) + 1 + (1))) + 1 + (1)) = 8

or, a different way of looking at it, the nodes are counted in this order :

2 1 6 4 7 8 3 5

Commented:
Nice guidance from Infinity08. Great contributor. =)

Commented:
Thanks! I understand them better now. =)
CERTIFIED EXPERT
Top Expert 2009

Commented:
Glad to have been of assistance :)
##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile