[aortell24]

Hello all I need to find the child nodes of a node in a binary tree.I was just wondering if this will return the number of child nodes thanks.

        public int FindChildNodes()
        {
            if (RightNode == null && LeftNode == null)
            {
                return 1;
            }
            else
            {
                return RightNode.FindChildNodes() + LeftNode.FindChildNodes();
            }
        }

[macosxnerd101]

First, you should always test your code. Second, your method won't work as intended because it only counts the leaves. You will want to return 1 + rightCount + leftCount, to include the current node as well.

[aortell24]

how about this?

 
public int FindChildNodes()
        {
            if (RightNode == null) 
            {
                return LeftNode.FindChildNodes() +  1;
            }
            else if (LeftNode == null)
            {
                return RightNode.FindChildNodes() + 1;
            }
            else if (LeftNode == null && RightNode == null)
            {
                return 1;
            }
            else 
            {
                return RightNode.FindChildNodes() + LeftNode.FindChildNodes();
            }
        }

[modi123_1]

Quote

how about this?

... what happens when you run it?

[macosxnerd101]

Nope. Because if both children are not null, you aren't counting the current Node.

By the way- why aren't you testing your code?

[aortell24]

I havent even written the tree class yet. I just wanted some one to take a quick look at it who know what they were doing.

[Momerath]

Code won't work if both nodes are null. Your first code was better, just needed to add 1 to the total returned in the last return statement.

And you aren't really finding the child nodes, you are finding the count of the descendant nodes.

[aortell24]

Thanks alot man I just wrote the tree class and it is off it is different each time I run it. I will give that a try Thanks again.

[aortell24]

It is working I am not sure how to mark this solved .Thanks guys

[AdamSpeight2008]

Shouldn't there a parameter to the function, say CurrentNode rather than two external variables LeftNode and RightNode ?

public int CountChildren( Node Current )
{
 if( Current == null ) return 0;
 /* etc */
}

Edit:
Depth-First Yielding of nodes.

Public IEnumerable< INode<T> > YieldChildren< T >(this Current : INode<T> ) 
{
  if( Current == null ) return Enumerable.Empty< T >();
  foreach( n in Current.LHS.YieldChildren() )
    Yield n;
  Yield Current;
  foreach( n in Current.RHS.YieldChildren() )
    Yield n;
}

Now you can use LINQ over the tree.

MyTree.TopNode.YieldChildren().Count()

This post has been edited by AdamSpeight2008: 31 December 2012 - 11:00 PM

[Momerath]

Wouldn't depth first have the 'yield current' last? Otherwise that looks just like an inorder traversal. But I do agree it should have parameters, otherwise he's just counting all the nodes (or doing something funky with the left/right node pointers that will bite him, or someone else, later) and it would be easier to just keep a count while you add them.

This post has been edited by Momerath: 01 January 2013 - 12:22 AM

[Skydiver]

The parameter is needed if you are looking at from the traditional C way to teaching data structures:

class Node
{
    public Node LeftNode;
    public Node RightNode;
}

class SomeClassThatUsesATree
{
    public int CountChildren(Node node)
    {
        :
    }
}

But if you look at it from the more modern object oriented view where classes are have state and behavior, then you can have:

class Node
{
    public Node LeftNode;
    public Node RightNode;

    public int CountChildren()
    {
        :
    }
}

[Momerath]

I think that gives the node too much information. There are trees that don't have the same types of nodes at each level and wouldn't know if those nodes can have children or not. I'd think the proper place to put the count would be in the tree in most cases (AVL, balanced trees being examples where the count might be in the node).

There is also the case where you convert a 'forest' into a single tree and traditionally, right nodes are at the same level so wouldn't be considered child nodes.

This post has been edited by Momerath: 01 January 2013 - 02:28 AM

[AdamSpeight2008]

Momerath, on 01 January 2013 - 08:20 AM, said:

Wouldn't depth first have the 'yield current' last? Otherwise that looks just like an inorder traversal.

Yep! It would but the example was more of a demonstration of using a parameter.

Skydiver I would use an Interface based Node Design.