I don't get what this does

[NoUserNameHere]

template <typename T>
int ct2 (tnode<T> *t)
{
int ctLeft, ctRight, ct;
if (t == NULL)
return 0;
else {
return ct2(t->left)+ct2(t->right)+
((t->left != NULL && t->right != NULL) ? 1 : 0);
}

I tried running it and I still can't figure out what it does. Specifically the return part in function ct2.

This is tnode.h :

#ifndef TREENODE
#define TREENODE

// represents a node in a binary tree
template <typename T>
class tnode
{
   public:

		T nodeValue;
		tnode<T> *left, *right;

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

		tnode (const T& item, tnode<T> *lptr = NULL, 
				 tnode<T> *rptr = NULL):
					nodeValue(item), left(lptr), right(rptr)
		{}
};

#endif

[ravenous]

It looks like it does something like counting all the nodes in a tree structure that have at two non-null child nodes. The return line is a relatively complex one, since it contains two recursive calls to ct2 and a ternary operator. Also, none of the variables declared on line 4 are used in the function either, which is a bit weird.

Basically, if you have a tree structure like this:

o
    / \
   /   \
  o     o
 / \   / \
o   o o   o
         / \
            o

If you pass the ct2 function the root node (the top one in the diagram above) then if this is null ct2 will immediately return 0 from line 6. If not, ct2 is called on the left child, since it's not null then ct2 gets called its left child node. This is also not null, so ct2 gets called on its left child node. The call stack now contains four calls to ct2 (the original one and three recursive calls from inside ct2 itself).

Now we're at the third row of the tree and the node we've called ct2 on its left child node, but it doesn't have one, so this is NULL and we again return 0 on line 6. Now, we've returned from the first call to ct2 on line 8. Now, the second call is executed (calling ct2 on the right node of the far left third row node). This node is also NULL, so we return 0. Now there's only the ternary operator to evaluate. Both of the child nodes of the current node (the far left node on the third row) are NULL, so this also evaluates to 0, and we can return back up to the far left second row node.

This process is repeated for the right child node of this row, which also returns 0, since its equivalent to the left. Now, when the ternary operator is evaluated for this node, both the child nodes are non-null, so this time it evaluates to 1. We therefore return 0 + 0 + 1 on line 8/9. (the zeros are from the calls to ct2 and the 1 is from the ternary operator). And so it progresses, until all the recursive calls to ct2 have returned. I think, in this case, the final result should be 3, since there are three nodes that have two non-null child nodes.

That's a little confusing, but recursive functions generally are!

Hope that helps :o)

[NoUserNameHere]

Oh.. that is a bit confusing. In general if there is something like

if(t != NULL)
{
functionName(t->left)
functionName(t->right)
somethingsomething
}

Does it mean that it goes to check all the nodes on the left side first and then right?

For the code in the first post, would it be correct to look at it like this?
http://i.imgur.com/d15z8.png

Meaning that it checks every node on the left first to see if it is NULL or not and then move on to the right side?