How to sum the determination of a pointer(s)

[ajj]

Hello All,

Yes this is homework, but I have spent a lot of time on it and I am
close.
I want to be able to count the number of nodes in a tree that have only
one child.

I can identify the nodes with the following code, but I don't know how
to sum them up and return that value to the calling function in main().
I know the algorithm is recursive in nature, but I get gibberish for
return values. I hope someone can please Help???

Here is the code and the calling function which sends the root of a
tree. I have tried iterating oneChildCount and it returns extremely
large values. The BST nodes are char.

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount, leftChildCount, rightChildCount;

if (t != NULL) // If it were NULL there would be no one child
nodes!
{

countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
oneChildCount = 1;
else
oneChildCount = 0;
cout << oneChildCount << endl;
return oneChildCount;

}

}

Calling Function is

cout << "Number of interior nodes with one child in Tree 1 is " <<
countOneChild (root1) << endl;

I would appreciate any help, Thanx in advance,
A.J. Johnston

[Ian Collins]

aj*@rextrax.com wrote:

Hello All,

Yes this is homework, but I have spent a lot of time on it and I am
close.
I want to be able to count the number of nodes in a tree that have only
one child.

I can identify the nodes with the following code, but I don't know how
to sum them up and return that value to the calling function in main().
I know the algorithm is recursive in nature, but I get gibberish for
return values. I hope someone can please Help???

Here is the code and the calling function which sends the root of a
tree. I have tried iterating oneChildCount and it returns extremely
large values. The BST nodes are char.

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount, leftChildCount, rightChildCount;

Avoid multiple declarations on one line, here you don't use
leftChildCount or rightChildCount.

if (t != NULL) // If it were NULL there would be no one child
nodes!
{

countOneChild(t->left); // descend left
countOneChild(t->right); // descend right

You don't do anything with the return values from these calls. I assume
you want to add them to oneChildCount.

>
if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
oneChildCount = 1;
else
oneChildCount = 0;
cout << oneChildCount << endl;
return oneChildCount;

}

}

If you want help with some code, you should post enough that it can be
compiled.

--
Ian Collins.

[ajj]

Hello Ian,

Here is my complete code. I followed your suggestions and cleaned up
the code quite a bit.
I want to evaluate a node, determine if it only has a left or right
child, if this is true I want to sum all of the nodes fitting the
description in variable oneChildCount. Then I want to return the
variable oneChildCount to main() and display the number of total nodes
that have only one child. The correct answer for each of the trees is
"2".

At the Bottom of my code is the two header files I am using. They seem
to be correct.
The compiler I am using is the bloodshed Dev-C++ 4.9.9.2 .

Thank you for the help
Sincerely,
A.J. Johnston

// Aaron Johnston
// CSIS 3402/01
// 07/06/06
// Problem # 35
// Page # 579

// This is a driver program that tests a function countOneChild
// The function counts the number of interior nodes in a
// binary tree having one child. The function will be tested in
// a program that uses buildTree() from "d_tnode1.h" to allocate
// Tree 1 and Tree 2. The function countOneChild() will be called
// once for each tree, and output the results.

#include <stdlib.h>
#include <iostream>

#ifndef NULL
#include <cstddef>
#endif // NULL

#include "d_tnode.h" // tnode class
#include "d_tnodel.h" // tnode library

using namespace std;

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount;

if (t != NULL) // If it were NULL there would be no one child
nodes!
{

if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
// associate the condition with the incrementation of a
variable,
// that is to say if child has only one node oneChildCount
should
// increase by 1, store the value, and be able to increase
again if
// necessary
// HOWEVER oneChildCount++ returns large numbers
// oneChildCount++;

oneChildCount = 1;
else
oneChildCount = 0;
// This statement confirms that one child nodes are
actually
// being found. And that two and zero child nodes exist.
cout << oneChildCount << endl;

// Tree traversal, is this correct?
countOneChild(t->left); // descend left
countOneChild(t->right); // descend right

// Returning the value of oneChildCount to main()
return oneChildCount;

}

}

int main()
{
// roots for two trees
tnode<char*root1, *root2;

// allocate Tree 1
root1 = buildTree(1);

// display Tree 1
cout << "Tree 1" << endl;
displayTree(root1, 1);
cout << endl << endl;

// allocate Tree 2
root2 = buildTree(2);

// display Tree 2
cout << "Tree 2" << endl;
displayTree(root2, 1);
cout << endl;

cout << "Number of interior nodes with one child in Tree 1 is " <<
countOneChild (root1) << endl;

cout << "Number of interior nodes with one child in Tree 2 is " <<
countOneChild (root2) << endl;
system("PAUSE");
return EXIT_SUCCESS;

return 0;
}

#ifndef TREENODE
#define TREENODE

// represents a node in a binary tree
template <typename T>
class tnode
{
public:
// tnode is a class implementation structure. making the
// data public simplifies building class functions
T nodeValue;
tnode<T*left, *right;

// default constructor. data not initialized
tnode()
{}

// initialize the data members
tnode (const T& item, tnode<T*lptr = NULL,
tnode<T*rptr = NULL):
nodeValue(item), left(lptr), right(rptr)
{}
};

#endif // TREENODE
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <queue>

#ifndef NULL
#include <cstddef>
#endif // NULL

#include "d_tnode.h" // use tnode class

using namespace std;

// objects hold a formatted label string and the level,column
// coordinates for a shadow tree node
class tnodeShadow
{
public:
string nodeValueStr; // formatted node value
int level,column;
tnodeShadow *left, *right;

tnodeShadow ()
{}
};

// create one of three binary trees with character data.
// the argument n selects from tree 0 - tree 2
tnode<char*buildTree(int n);

// inorder recursive output of the nodes in a binary tree.
// output separator after each node value. default value
// of separator is " "
template <typename T>
void inorderOutput(tnode<T*t, const string& separator = " ");

// postorder recursive output of the nodes in a binary tree.
// output separator after each node value. default value
// of separator is " "
template <typename T>
void postorderOutput(tnode<T*t, const string& separator = " ");

// traverse the tree level by level and output each node in a
// binary tree. output separator after each node value. default value
// of separator is " "
template <typename T>
void levelorderOutput(tnode<T*t, const string& separator = " ");

// accumulate the number of leaf nodes in count
template <typename T>
void countLeaf(tnode<T*t, int& count);

// return the depth of the binary tree
template <typename T>
int depth (tnode<T*t);

// create copy of tree t and return a pointer to the new root
template <typename T>
tnode<T*copyTree(tnode<T*t);

// traverse the nodes in the binary tree and delete each node
template <typename T>
void deleteTree(tnode<T*t);

// delete all tree nodes using deleteTree() and then assign
// t to be NULL
template <typename T>
void clearTree(tnode<T* & t);

// recursive inorder scan used to build the shadow tree
template <typename T>
tnodeShadow *buildShadowTree(tnode<T*t, int level, int& column);

// display a binary tree. output of a node value requires
// no more than maxCharacters
template <typename T>
void displayTree(tnode<T*t, int maxCharacters);

// delete the nodes in the shadow tree
void deleteShadowTree(tnodeShadow *t);

tnode<char*buildTree(int n)
{
// 9 tnode pointers; points to the 9 items in the tree
tnode<char*root, *b, *c, *d, *e, *f, *g, *h, *i;

// parameter n specifies a tree in the range 0 - 2
switch(n)
{
// nodes d and e are leaf nodes replace D E B C A
case 0:
d = new tnode<char('D');
e = new tnode<char('E');
b = new tnode<char('B',(tnode<char*)NULL, d);
c = new tnode<char('C',e, (tnode<char*)NULL);
root = new tnode<char('A',b, c);
break;

// nodes g, h, i, and d are leaf nodes
case 1:
g = new tnode<char('G');
h = new tnode<char('H');
i = new tnode<char('I');
d = new tnode<char('D');
e = new tnode<char('E',g, (tnode<char*)NULL);
f = new tnode<char('F',h, i);
b = new tnode<char('B',d, e);
c = new tnode<char('C',(tnode<char*)NULL, f);
root = new tnode<char('A',b, c);
break;

// nodes g, h, i and f are leaf nodes
case 2:
g = new tnode<char('G');
h = new tnode<char('H');
i = new tnode<char('I');
d = new tnode<char('D',(tnode<char*)NULL, g);
e = new tnode<char('E',h, i);
f = new tnode<char('F');
b = new tnode<char('B',d, (tnode<char*)NULL);
c = new tnode<char('C',e, f);
root = new tnode<char('A',b, c);
break;
}

return root;
}


template <typename T>
void inorderOutput(tnode<T*t, const string& separator)
{
// the recursive scan terminates on a empty subtree
if (t != NULL)
{
inorderOutput(t->left, separator); // descend left
cout << t->nodeValue << separator; // output the node
inorderOutput(t->right, separator); // descend right
}
}

template <typename T>
void postorderOutput(tnode<T*t, const string& separator)
{
// the recursive scan terminates on a empty subtree
if (t != NULL)
{
postorderOutput(t->left, separator); // descend left
postorderOutput(t->right, separator); // descend right
cout << t->nodeValue << separator; // output the node
}
}

template <typename T>
void levelorderOutput(tnode<T*t, const string& separator)
{
// store siblings of each node in a queue so that they are
// visited in order at the next level of the tree
queue<tnode<T*q;
tnode<T*p;

// initialize the queue by inserting the root in the queue
q.push(t);

// continue the iterative process until the queue is empty
while(!q.empty())
{
// delete front node from queue and output the node value
p = q.front();
q.pop();
cout << p->nodeValue << separator;

// if a left child exists, insert it in the queue
if(p->left != NULL)
q.push(p->left);
// if a right child exists, insert next to its sibling
if(p->right != NULL)
q.push(p->right);
}
}

// assume that count initialized to 0
template <typename T>
void countLeaf (tnode<T*t, int& count)
{
if (t != NULL)
{
// check if t is a leaf node (no children).
// if so, increment count
if (t->left == NULL && t->right == NULL)
count++;

countLeaf(t->left, count); // descend left
countLeaf(t->right, count); // descend right
}
}
// determine the depth of the tree using a postorder scan
template <typename T>
int depth (tnode<T*t)
{
int depthLeft, depthRight, depthval;

if (t == NULL)
// depth of an empty tree is -1
depthval = -1;
else
{
// find the depth of the left subtree of t
depthLeft= depth(t->left);
// find the depth of the right subtree of t
depthRight= depth(t->right);
// depth of the tree with root t is 1 + maximum
// of the depths of the two subtrees
depthval = 1 +
(depthLeft depthRight ? depthLeft : depthRight);
}

return depthval;
}

template <typename T>
tnode<T*copyTree(tnode<T*t)
{
// newNode points at a new node that the algorithm
// creates. newLptr. and newRptr point to the subtrees
// of newNode
tnode<T*newLeft, *newRight, *newNode;

// stop the recursive scan when we arrive at empty tree
if (t == NULL)
return NULL;

// build the new tree from the bottom up by building the two
// subtrees and then building the parent. at node t, make
// a copy of the left subtree and assign its root node pointer
// to newLeft. make a copy of the right subtree and assign its
// root node pointer to newRight
newLeft = copyTree(t->left);
newRight = copyTree(t->right);

// create a new node whose value is the same as the value in t
// and whose children are the copied subtrees
newNode = new tnode<T(t->nodeValue, newLeft, newRight);

// return a pointer to the root of the newly copied tree
return newNode;
}

template <typename T>
void deleteTree(tnode<T*t)
{
// postorder scan. delete left and right
// subtrees of t and then node t
if (t != NULL)
{
deleteTree(t->left);
deleteTree(t->right);
delete t;
}
}

template <typename T>
void clearTree(tnode<T* & t)
{
deleteTree(t);
t = NULL;
}

template <typename T>
tnodeShadow *buildShadowTree(tnode<T*t, int level, int& column)
{
// pointer to new shadow tree node
tnodeShadow *newNode = NULL;
// ostr used to perform format conversion
ostringstream ostr;

if (t != NULL)
{
// create the new shadow tree node
newNode = new tnodeShadow;

// allocate node for left child at next level in tree; attach node
tnodeShadow *newLeft = buildShadowTree(t->left, level+1, column);
newNode->left = newLeft;

// initialize data members of the new node
ostr << t->nodeValue << ends; // format conversion
newNode->nodeValueStr = ostr.str();
newNode->level = level;
newNode->column = column;

// update column to next cell in the table
column++;

// allocate node for right child at next level in tree; attach node
tnodeShadow *newRight = buildShadowTree(t->right, level+1, column);
newNode->right = newRight;
}

return newNode;
}

template <typename T>
void displayTree(tnode<T*t, int maxCharacters)
{
string label;
int level = 0, column = 0;
int colWidth = maxCharacters + 1;
//
int currLevel = 0, currCol = 0;

if (t == NULL)
return;

// build the shadow tree
tnodeShadow *shadowRoot = buildShadowTree(t, level, column);

// use during the level order scan of the shadow tree
tnodeShadow *currNode;

// store siblings of each tnodeShadow object in a queue so that
// they are visited in order at the next level of the tree
queue<tnodeShadow *q;

// insert the root in the queue and set current level to 0
q.push(shadowRoot);

// continue the iterative process until the queue is empty
while(!q.empty())
{
// delete front node from queue and make it the current node
currNode = q.front();
q.pop();

// if level changes, output a newline
if (currNode->level currLevel)
{
currLevel = currNode->level;
currCol = 0;
cout << endl;
}

// if a left child exists, insert the child in the queue
if(currNode->left != NULL)
q.push(currNode->left);

// if a right child exists, insert the child in the queue
if(currNode->right != NULL)
q.push(currNode->right);

// output formatted node label
if (currNode->column currCol)
{
cout << setw((currNode->column-currCol)*colWidth) << " ";
currCol = currNode->column;
}
cout << setw(colWidth) << currNode->nodeValueStr;
currCol++;
}
cout << endl;

// delete the shadow tree
deleteShadowTree(shadowRoot);
}

void deleteShadowTree(tnodeShadow *t)
{
// if current root node is not NULL, delete its left subtree,
// its right subtree and then the node itself
if (t != NULL)
{
deleteShadowTree(t->left);
deleteShadowTree(t->right);
delete t;
}
}

#endif // TREE_LIBRARY_FUNCTIONS

[jbannon]

aj*@rextrax.com wrote:

Hello All,

Yes this is homework, but I have spent a lot of time on it and I am
close.
I want to be able to count the number of nodes in a tree that have only
one child.

I can identify the nodes with the following code, but I don't know how
to sum them up and return that value to the calling function in main().
I know the algorithm is recursive in nature, but I get gibberish for
return values. I hope someone can please Help???

Here is the code and the calling function which sends the root of a
tree. I have tried iterating oneChildCount and it returns extremely
large values. The BST nodes are char.

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount, leftChildCount, rightChildCount;

if (t != NULL) // If it were NULL there would be no one child
nodes!
{

countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
oneChildCount = 1;
else
oneChildCount = 0;
cout << oneChildCount << endl;
return oneChildCount;

}

}

Calling Function is

cout << "Number of interior nodes with one child in Tree 1 is " <<
countOneChild (root1) << endl;

I would appreciate any help, Thanx in advance,
A.J. Johnston

I'm not surprised since you haven't initialised any of the local
variables. The compiler will allocate storage for them but the value
can be anything and you want them all to be specifically 0, at least
initially. Declare them like this:

int oneChildCount(0);
int leftChildCount(0);
int rightChildCount(0);

This will guarantee that the counts have sensible values on function
entry.

Why have you declared leftChildCount and rightChildCount when they do
not appear to be used within the function?

oneChildCount does not appear to be incremented anywhere. Presumably,
you want to count the number of tree nodes having just one child? As
far as I can see oneChildCount will either have a nonsense value or 1
for each recursive invocation of countOneChild whereas it should be
zero initially and then increment for each tnode having only one child.
The function would then return 0 (there are no one child nodes) or some
positive number equal to the number of one child nodes in the tree.

There is also no return statement at the end of the function. What
happens if t happens to be zero? What value is returned? There is no
gurantee that the function will return anything sensible.

The function does not modify a tnode so why isn't the argument declared
as tnode<Tconst* instead of tnode<T>* ?

I wouldn't use a plain int here since: a) you don't know its size and
it might overflow for large trees; and b) it's not really what you
want. What you want is a count type - yes it's a number but it's closer
to the problem domain. I would do something like:

typedef std::size_t TreeNodeCount;

and then declare the function to be of type TreeNodeCount. You could do
this like this:

template <typename T>
TreeNodeCount countOneChild (TreeNode<Tconst& treeNode);

since countOneChild will never modify a tree node and, presumably, will
not alter the internal state of the class. Note that I have used a
reference rather than a pointer here. You would need to modify the code
to take account of that or just use the pointer.

Why are you using the NULL macro? There is no need to since the
standard guarantees that binary 0 is compatible with any pointer. NULL
is a hangover from C and this is C++.

I haven't gone through the other code but hopefully this will help.

Best regards
Jim Bannon.

[ajj]

Jim, you have some good points

Declare them like this:

int oneChildCount(0);

Done.

Why have you declared leftChildCount and rightChildCount when they

do

not appear to be used within the function?

These variables have been deleted, they were used in a former version

oneChildCount does not appear to be incremented anywhere. Presumably,
you want to count the number of tree nodes having just one child? As
far as I can see oneChildCount will either have a nonsense value or 1
for each recursive invocation of countOneChild whereas it should be
zero initially and then increment for each tnode having only one child.
The function would then return 0 (there are no one child nodes) or some
positive number equal to the number of one child nodes in the tree.

I am now incrementing oneChildCount as follows
oneChildCount++;

>
There is also no return statement at the end of the function. What
happens if t happens to be zero? What value is returned? There is no
gurantee that the function will return anything sensible.

I am using the statement
return oneChildCount;

>
The function does not modify a tnode so why isn't the argument declared
as tnode<Tconst* instead of tnode<T>* ?

Defined parameter. May not be modified.

>
I wouldn't use a plain int here since: a) you don't know its size and
it might overflow for large trees; and b) it's not really what you
want. What you want is a count type - yes it's a number but it's closer
to the problem domain. I would do something like:

typedef std::size_t TreeNodeCount;

and then declare the function to be of type TreeNodeCount. You could do
this like this:

template <typename T>
TreeNodeCount countOneChild (TreeNode<Tconst& treeNode);

since countOneChild will never modify a tree node and, presumably, will
not alter the internal state of the class. Note that I have used a
reference rather than a pointer here. You would need to modify the code
to take account of that or just use the pointer.

I have successfuly implemented a solution in this fashion (the one with
a reference) however, I am unable to find a solution with the
requirements listed below.

Write a function

template <typename T>
int countOneChild(tnode<T*t);
that counts the number of interior nodes in a binary tree having one
child.

If you look at the previous code you will see that these nodes can be
identified as well as the tree traversal through the output. The
problem is the sum algorithm. Why am I able to correctly identify a
one child node, increment a variable, only to have that variable
reinitialized to zero? What am I failing to understand about pointers?

>
Why are you using the NULL macro? There is no need to since the
standard guarantees that binary 0 is compatible with any pointer. NULL
is a hangover from C and this is C++.

Good to know :)
Good point!
Eradicated

>

There are no compilation errors

Any more help would be wonderful!!!

Sincerely,
Aaron Johnston

[jbannon]

aj*@rextrax.com wrote:

Jim, you have some good points

Declare them like this:

int oneChildCount(0);

Done.

Why have you declared leftChildCount and rightChildCount when they

do

not appear to be used within the function?

These variables have been deleted, they were used in a former version

oneChildCount does not appear to be incremented anywhere. Presumably,
you want to count the number of tree nodes having just one child? As
far as I can see oneChildCount will either have a nonsense value or 1
for each recursive invocation of countOneChild whereas it should be
zero initially and then increment for each tnode having only one child.
The function would then return 0 (there are no one child nodes) or some
positive number equal to the number of one child nodes in the tree.

I am now incrementing oneChildCount as follows
oneChildCount++;

There is also no return statement at the end of the function. What
happens if t happens to be zero? What value is returned? There is no
gurantee that the function will return anything sensible.

I am using the statement
return oneChildCount;

The function does not modify a tnode so why isn't the argument declared
as tnode<Tconst* instead of tnode<T>* ?

Defined parameter. May not be modified.

I wouldn't use a plain int here since: a) you don't know its size and
it might overflow for large trees; and b) it's not really what you
want. What you want is a count type - yes it's a number but it's closer
to the problem domain. I would do something like:

typedef std::size_t TreeNodeCount;

and then declare the function to be of type TreeNodeCount. You could do
this like this:

template <typename T>
TreeNodeCount countOneChild (TreeNode<Tconst& treeNode);

since countOneChild will never modify a tree node and, presumably, will
not alter the internal state of the class. Note that I have used a
reference rather than a pointer here. You would need to modify the code
to take account of that or just use the pointer.

I have successfuly implemented a solution in this fashion (the one with
a reference) however, I am unable to find a solution with the
requirements listed below.

Write a function

template <typename T>
int countOneChild(tnode<T*t);
that counts the number of interior nodes in a binary tree having one
child.

If you look at the previous code you will see that these nodes can be
identified as well as the tree traversal through the output. The
problem is the sum algorithm. Why am I able to correctly identify a
one child node, increment a variable, only to have that variable
reinitialized to zero? What am I failing to understand about pointers?

Why are you using the NULL macro? There is no need to since the
standard guarantees that binary 0 is compatible with any pointer. NULL
is a hangover from C and this is C++.

Good to know :)
Good point!
Eradicated

There are no compilation errors

Any more help would be wonderful!!!

Sincerely,
Aaron Johnston

Aaron,
I'm only at the beginning stage myself and it is some time since I
looked at recursive functions, but I'll have a go. I think that the
problem lies in what happens to count across recursive calls. The
question we should ask is the value of oneChildCount preserved across
recursive invocations of the function? I'm trying to remember recursive
function theory and I think that the value of count is not preserved
(the experts will crucify me if I'm wrong). Each time the function
recurses, a new copy of count is pushed onto the stack as part of the
stack frame so this would indicate that our count needs to be of static
storage duration. Therefore, modifying our declaration of count to be
something like

static int oneChildCount(0);

should solve the problem. This means that whenever we execute the
statement ++oneChildCount; it is the static variable that is being
updated preserving its value across recursive invocations. The final
statement in the function should then be return oneChildCount;

What's worrying me though is what happens when we call the function
again with a different node. Since this would effectively be a new
execution environment it should reset oneChildCount but I'm not sure.
Any expert opinion please?

P.S. I would modify the function slightly to eliminate the 2 simplest
cases first: a null node; and a node with no children. I would do this
before attempting a recursive call like this:

if (t == 0)
{ // empty tree
return 0;
}

if ((t->left == 0) && (t->right ==0))
{ // single node with no children
return 0;
}

Also, if we want to be "cute" we can take advantage of the
short-circuit nature of boolean operators in C++ (assuming they haven't
been overloaded for this class) and collapse the two tests into 1 as
follows:

if ((t == 0) || ((t->left == 0) && (t->right == 0)))
return 0;

Note how we can get way with this here because short-circuit rules
guarantee left-to-right evaluation order. In other languages where
short-circuit evaluation is not done this would likely generate a core
dump since the second half of the expression might be referencing
through a null pointer if t is actually 0.

Of course this violates the one-entry : one-exit rule of structured
programing and your teacher might not find that acceptable. He / she
might not accept relying on short-circuit evaluation order either since
it may cause confusion in other circumstances (remember that in general
C++ does not guarantee that an arbitrary expression will be evaluated
in a specific order). Don't do this if you're in any doubt about what
your teacher will accept!

Hope this helps.

Cheers
Jim.

[jbannon]

jbannon wrote:

aj*@rextrax.com wrote:

Jim, you have some good points

Declare them like this:
>
int oneChildCount(0);
>

Done.

Why have you declared leftChildCount and rightChildCount when they

do

not appear to be used within the function?

These variables have been deleted, they were used in a former version

oneChildCount does not appear to be incremented anywhere. Presumably,
you want to count the number of tree nodes having just one child? As
far as I can see oneChildCount will either have a nonsense value or 1
for each recursive invocation of countOneChild whereas it should be
zero initially and then increment for each tnode having only one child.
The function would then return 0 (there are no one child nodes) or some
positive number equal to the number of one child nodes in the tree.

I am now incrementing oneChildCount as follows
oneChildCount++;

>
There is also no return statement at the end of the function. What
happens if t happens to be zero? What value is returned? There is no
gurantee that the function will return anything sensible.

I am using the statement
return oneChildCount;

>
The function does not modify a tnode so why isn't the argument declared
as tnode<Tconst* instead of tnode<T>* ?

Defined parameter. May not be modified.

>
I wouldn't use a plain int here since: a) you don't know its size and
it might overflow for large trees; and b) it's not really what you
want. What you want is a count type - yes it's a number but it's closer
to the problem domain. I would do something like:
>
typedef std::size_t TreeNodeCount;
>
and then declare the function to be of type TreeNodeCount. You could do
this like this:
>
template <typename T>
TreeNodeCount countOneChild (TreeNode<Tconst& treeNode);
>
since countOneChild will never modify a tree node and, presumably, will
not alter the internal state of the class. Note that I have used a
reference rather than a pointer here. You would need to modify the code
to take account of that or just use the pointer.

I have successfuly implemented a solution in this fashion (the one with
a reference) however, I am unable to find a solution with the
requirements listed below.

Write a function

template <typename T>
int countOneChild(tnode<T*t);
that counts the number of interior nodes in a binary tree having one
child.

If you look at the previous code you will see that these nodes can be
identified as well as the tree traversal through the output. The
problem is the sum algorithm. Why am I able to correctly identify a
one child node, increment a variable, only to have that variable
reinitialized to zero? What am I failing to understand about pointers?

>
Why are you using the NULL macro? There is no need to since the
standard guarantees that binary 0 is compatible with any pointer. NULL
is a hangover from C and this is C++.

Good to know :)
Good point!
Eradicated

>

There are no compilation errors

Any more help would be wonderful!!!

Sincerely,
Aaron Johnston

Aaron,
I'm only at the beginning stage myself and it is some time since I
looked at recursive functions, but I'll have a go. I think that the
problem lies in what happens to count across recursive calls. The
question we should ask is the value of oneChildCount preserved across
recursive invocations of the function? I'm trying to remember recursive
function theory and I think that the value of count is not preserved
(the experts will crucify me if I'm wrong). Each time the function
recurses, a new copy of count is pushed onto the stack as part of the
stack frame so this would indicate that our count needs to be of static
storage duration. Therefore, modifying our declaration of count to be
something like

static int oneChildCount(0);

should solve the problem. This means that whenever we execute the
statement ++oneChildCount; it is the static variable that is being
updated preserving its value across recursive invocations. The final
statement in the function should then be return oneChildCount;

What's worrying me though is what happens when we call the function
again with a different node. Since this would effectively be a new
execution environment it should reset oneChildCount but I'm not sure.
Any expert opinion please?

P.S. I would modify the function slightly to eliminate the 2 simplest
cases first: a null node; and a node with no children. I would do this
before attempting a recursive call like this:

if (t == 0)
{ // empty tree
return 0;
}

if ((t->left == 0) && (t->right ==0))
{ // single node with no children
return 0;
}

Also, if we want to be "cute" we can take advantage of the
short-circuit nature of boolean operators in C++ (assuming they haven't
been overloaded for this class) and collapse the two tests into 1 as
follows:

if ((t == 0) || ((t->left == 0) && (t->right == 0)))
return 0;

Note how we can get way with this here because short-circuit rules
guarantee left-to-right evaluation order. In other languages where
short-circuit evaluation is not done this would likely generate a core
dump since the second half of the expression might be referencing
through a null pointer if t is actually 0.

Of course this violates the one-entry : one-exit rule of structured
programing and your teacher might not find that acceptable. He / she
might not accept relying on short-circuit evaluation order either since
it may cause confusion in other circumstances (remember that in general
C++ does not guarantee that an arbitrary expression will be evaluated
in a specific order). Don't do this if you're in any doubt about what
your teacher will accept!

Hope this helps.

Cheers
Jim.

Nuts! I boobed! Ignore the last bit as it's not correct. What happens
if, during a recursive invocation, both t->left and t->right are 0?
What we should do is return the value of oneChildCount, not 0!
Apologies. Sheesh!

[ajj]

Aaron,

I'm only at the beginning stage myself and it is some time since I
looked at recursive functions, but I'll have a go. I think that the
problem lies in what happens to count across recursive calls. The
question we should ask is the value of oneChildCount preserved across
recursive invocations of the function? I'm trying to remember recursive
function theory and I think that the value of count is not preserved
(the experts will crucify me if I'm wrong). Each time the function
recurses, a new copy of count is pushed onto the stack as part of the
stack frame so this would indicate that our count needs to be of static
storage duration. Therefore, modifying our declaration of count to be
something like

static int oneChildCount(0);

should solve the problem. This means that whenever we execute the
statement ++oneChildCount; it is the static variable that is being
updated preserving its value across recursive invocations. The final
statement in the function should then be return oneChildCount;

What's worrying me though is what happens when we call the function
again with a different node. Since this would effectively be a new
execution environment it should reset oneChildCount but I'm not sure.
Any expert opinion please?

The static int was a good idea, the value is persistent though, and so
subsequent calls to the same function are summed. So in this case the
second call would start with oneChildCount with a value of "2." Any
more ideas. I really do appreciate all the help so far.

Aaron Johnston

Also, if we want to be "cute" we can take advantage of the
short-circuit nature of boolean operators in C++ (assuming they haven't
been overloaded for this class) and collapse the two tests into 1 as
follows:

if ((t == 0) || ((t->left == 0) && (t->right == 0)))
return oneChildCount;

This is fine and good programming practice as far as I understand.

The situation most likely to occur should be stated on the left,
so that if it is true, the right side not even need be evaluated.

The static int was a good idea, the value is persistent though, and so
subsequent calls to the same function are summed. So in this case the
second call would start with oneChildCount with a value of "2." Any
more ideas. I really do appreciate all the help so far.

Aaron Johnston

[jbannon]

aj*@rextrax.com wrote:

Aaron,
I'm only at the beginning stage myself and it is some time since I
looked at recursive functions, but I'll have a go. I think that the
problem lies in what happens to count across recursive calls. The
question we should ask is the value of oneChildCount preserved across
recursive invocations of the function? I'm trying to remember recursive
function theory and I think that the value of count is not preserved
(the experts will crucify me if I'm wrong). Each time the function
recurses, a new copy of count is pushed onto the stack as part of the
stack frame so this would indicate that our count needs to be of static
storage duration. Therefore, modifying our declaration of count to be
something like
>
static int oneChildCount(0);
>
should solve the problem. This means that whenever we execute the
statement ++oneChildCount; it is the static variable that is being
updated preserving its value across recursive invocations. The final
statement in the function should then be return oneChildCount;
>
What's worrying me though is what happens when we call the function
again with a different node. Since this would effectively be a new
execution environment it should reset oneChildCount but I'm not sure.
Any expert opinion please?

The static int was a good idea, the value is persistent though, and so
subsequent calls to the same function are summed. So in this case the
second call would start with oneChildCount with a value of "2." Any
more ideas. I really do appreciate all the help so far.

Aaron Johnston

>
>
Also, if we want to be "cute" we can take advantage of the
short-circuit nature of boolean operators in C++ (assuming they haven't
been overloaded for this class) and collapse the two tests into 1 as
follows:
>
if ((t == 0) || ((t->left == 0) && (t->right == 0)))
return oneChildCount;
>
This is fine and good programming practice as far as I understand.

The situation most likely to occur should be stated on the left,
so that if it is true, the right side not even need be evaluated.

The static int was a good idea, the value is persistent though, and so
subsequent calls to the same function are summed. So in this case the
second call would start with oneChildCount with a value of "2." Any
more ideas. I really do appreciate all the help so far.

Aaron Johnston

Aaron,
We're missing something really obvious but for the life of me I can't
see what it is. A really silly test confirms the suspicion:

#include <iostream>

int recurse(int n)
{
static int t(0);
++t;
std::cout << "Value of t is " << t << std::endl;
if (n == 0)
return t;
recurse (--n);
}

int main()
{
int t1(0);
t1 = recurse(10);
std::cout << "Value of t1 is " << t1 << std::endl;

t1 = recurse(10);
std::cout << "Value of t1 is " << t1 << std::endl;

return 0;
}

The problem here is that, as you rightly say, the value continues to
accumulate on any subsequent calls and yet, if we remove the static
storage specifier the value of t is always 1. Of course, I have not
checked for negative n, in which case we would get an infinite loop,
but that does not really matter here.

I don't think the problem lies in the method of tree traversal. We
could do an in-order, pre-order or post-order traversal and end up with
the same result so it's not that. But I cannot for the life of me see a
way of preserving the count using a recursive traversal algorithm that
clears the count on subsequent calls with a new node. Maybe we should
be looking at non-recursive methods?

[tragomaskhalos]

jbannon wrote:

aj*@rextrax.com wrote:

Aaron,
I'm only at the beginning stage myself and it is some time since I
looked at recursive functions, but I'll have a go. I think that the
problem lies in what happens to count across recursive calls. The
question we should ask is the value of oneChildCount preserved across
recursive invocations of the function? I'm trying to remember recursive
function theory and I think that the value of count is not preserved
(the experts will crucify me if I'm wrong). Each time the function
recurses, a new copy of count is pushed onto the stack as part of the
stack frame so this would indicate that our count needs to be of static
storage duration. Therefore, modifying our declaration of count to be
something like

static int oneChildCount(0);

This is a bad idea - try passing an object down through the recursion
to accumulate the count; google for the "visitor" pattern.

[jbannon]

tragomaskhalos wrote:

jbannon wrote:

aj*@rextrax.com wrote:

Aaron,
I'm only at the beginning stage myself and it is some time since I
looked at recursive functions, but I'll have a go. I think that the
problem lies in what happens to count across recursive calls. The
question we should ask is the value of oneChildCount preserved across
recursive invocations of the function? I'm trying to remember recursive
function theory and I think that the value of count is not preserved
(the experts will crucify me if I'm wrong). Each time the function
recurses, a new copy of count is pushed onto the stack as part of the
stack frame so this would indicate that our count needs to be of static
storage duration. Therefore, modifying our declaration of count to be
something like
>
static int oneChildCount(0);
>

This is a bad idea - try passing an object down through the recursion
to accumulate the count; google for the "visitor" pattern.

Yeah, a visitor would do the job (having just looked it up). Don't
quite know how it would be done though but it's worth having a go.

Thanks
Jim.

[James Bannon]

aj*@rextrax.com wrote:

Hello All,

Yes this is homework, but I have spent a lot of time on it and I am
close.
I want to be able to count the number of nodes in a tree that have only
one child.

I can identify the nodes with the following code, but I don't know how
to sum them up and return that value to the calling function in main().
I know the algorithm is recursive in nature, but I get gibberish for
return values. I hope someone can please Help???

Here is the code and the calling function which sends the root of a
tree. I have tried iterating oneChildCount and it returns extremely
large values. The BST nodes are char.

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount, leftChildCount, rightChildCount;

if (t != NULL) // If it were NULL there would be no one child
nodes!
{

countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
oneChildCount = 1;
else
oneChildCount = 0;
cout << oneChildCount << endl;
return oneChildCount;

}

}

Calling Function is

cout << "Number of interior nodes with one child in Tree 1 is " <<
countOneChild (root1) << endl;

I would appreciate any help, Thanx in advance,
A.J. Johnston

Aaron
I've been having a little think about this. What would happen if we wrapped the
template function in an auxilliary class whose state was the actual count you're
looking for? Something like the following I believe would work (note I haven't tested
this or fleshed out the details):

template< typename T >
class CountChildren
{
public:
CountChildren ()
: oneChildNodes(0), leftChildNodes(0), rightChildNodes(0) {}
size_t oneChildCount (T const& node);
size_t leftChildCount (T const& node);
size_t rightChildCount (T const& node);
~CountChildren () {}

private:
size_t oneChildNodes_;
size_t leftChildNodes_;
size_t rightChildNodes_;
};

The destructor doesn't really need to do anything very much since we're only dealing
with simple integral types.
Implementation of the functions would then follow the recursive tree traversal method
already discussed except that instead of updating a static variable, they update the
private counts.

Anyone any thoughts on this strategy?

Cheers
Jim.

[James Bannon]

James Bannon wrote:

aj*@rextrax.com wrote:

>Hello All,

Yes this is homework, but I have spent a lot of time on it and I am
close.
I want to be able to count the number of nodes in a tree that have only
one child.

I can identify the nodes with the following code, but I don't know how
to sum them up and return that value to the calling function in main().
I know the algorithm is recursive in nature, but I get gibberish for
return values. I hope someone can please Help???

Here is the code and the calling function which sends the root of a
tree. I have tried iterating oneChildCount and it returns extremely
large values. The BST nodes are char.

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount, leftChildCount, rightChildCount;

if (t != NULL) // If it were NULL there would be no one child
nodes!
{

countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
oneChildCount = 1;
else
oneChildCount = 0;
cout << oneChildCount << endl;
return oneChildCount;

}

}

Calling Function is

cout << "Number of interior nodes with one child in Tree 1 is " <<
countOneChild (root1) << endl;
I would appreciate any help, Thanx in advance,
A.J. Johnston

Aaron
I've been having a little think about this. What would happen if we
wrapped the template function in an auxilliary class whose state was the
actual count you're looking for? Something like the following I believe
would work (note I haven't tested this or fleshed out the details):

template< typename T >
class CountChildren
{
public:
CountChildren ()
: oneChildNodes(0), leftChildNodes(0), rightChildNodes(0) {}
size_t oneChildCount (T const& node);
size_t leftChildCount (T const& node);
size_t rightChildCount (T const& node);
~CountChildren () {}

private:
size_t oneChildNodes_;
size_t leftChildNodes_;
size_t rightChildNodes_;
};

The destructor doesn't really need to do anything very much since we're
only dealing with simple integral types.
Implementation of the functions would then follow the recursive tree
traversal method already discussed except that instead of updating a
static variable, they update the private counts.

Anyone any thoughts on this strategy?

Cheers
Jim.

Correction. The constructor should read:

CountChildren(): oneChildNodes_(0), leftChildNodes_(0), rightChildNodes(0) {}

Sorry about that!

Cheers
Jim

[vacu]

A,J

I think you need to modify this function like this:

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount(0;

if (t != NULL) // If it were NULL there would be no one child
nodes!
{
countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL){
oneChildCount = countOneChild(t->left) + 1; //descend left
}
else if ((t->left == NULL&& t->right != NULL)){
oneChildeCount++;
oneChildCount += countOneChild(t->right); //descend right
}
else
oneChildCount += (countOneChild(t->left) +
countOneChilde(t->right));

}
cout << oneChildCount << endl;
return oneChildCount;
}

Sorry, I did't test it with your other code.
Vacu

[Christopher Benson-Manica]

vacu <va*****@gmail.comwrote:

A,J

I think you need to modify this function like this:

AJ, and the rest of the group, would have been better served had you
quoted the relevant portions of the article you replied to; as it is,
it isn't at all clear what "this function" is.

Please read http://cfaj.freeshell.org/google/.

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

[vacu]

Reposting with quotate text and clarify *this function" to actual
function name, hope it is clear this time.
A,J

I think you need to modify template <typename Tint
countOneChild(tnode<T*t)
function like this:
template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount(0;
if (t != NULL) // If it were NULL there would be no one child
nodes!
{
countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL){
oneChildCount = countOneChild(t->left) + 1; //descend left

}
else if ((t->left == NULL&& t->right != NULL)){
oneChildeCount++;
oneChildCount += countOneChild(t->right); //descend right
}
else
oneChildCount += (countOneChild(t->left) +
countOneChilde(t->right));
}
cout << oneChildCount << endl;
return oneChildCount;
}
Sorry, I did't test it with your other code.
Vacu

aj*@rextrax.com wrote:

Hello All,

Yes this is homework, but I have spent a lot of time on it and I am
close.
I want to be able to count the number of nodes in a tree that have only
one child.

I can identify the nodes with the following code, but I don't know how
to sum them up and return that value to the calling function in main().
I know the algorithm is recursive in nature, but I get gibberish for
return values. I hope someone can please Help???

Here is the code and the calling function which sends the root of a
tree. I have tried iterating oneChildCount and it returns extremely
large values. The BST nodes are char.

template <typename T>
int countOneChild(tnode<T*t)
{
int oneChildCount, leftChildCount, rightChildCount;

if (t != NULL) // If it were NULL there would be no one child
nodes!
{

countOneChild(t->left); // descend left
countOneChild(t->right); // descend right
if ((t->left != NULL && t->right == NULL) || (t->left == NULL
&& t->right != NULL))
oneChildCount = 1;
else
oneChildCount = 0;
cout << oneChildCount << endl;
return oneChildCount;

}

}

Calling Function is

cout << "Number of interior nodes with one child in Tree 1 is " <<
countOneChild (root1) << endl;
I would appreciate any help, Thanx in advance,
A.J. Johnston