# Finding child Nodes of a node in a tree

Page 1 of 1

## 13 Replies - 872 Views - Last Post: 01 January 2013 - 12:22 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=305294&amp;s=443185b14c4dc0e2c92f6b0b8187b123&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 aortell24

Reputation: 0
• Posts: 18
• Joined: 07-December 12

# Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:12 PM

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();
}
}

```

Is This A Good Question/Topic? 0

## Replies To: Finding child Nodes of a node in a tree

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12302
• Posts: 45,400
• Joined: 27-December 08

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:13 PM

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.

### #3 aortell24

Reputation: 0
• Posts: 18
• Joined: 07-December 12

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:19 PM

```
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();
}
}

```

### #4 modi123_1

• Suitor #2

Reputation: 14039
• Posts: 56,188
• Joined: 12-June 08

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:19 PM

Quote

... what happens when you run it?

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12302
• Posts: 45,400
• Joined: 27-December 08

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:20 PM

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?

### #6 aortell24

Reputation: 0
• Posts: 18
• Joined: 07-December 12

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:22 PM

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.

### #7 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• Joined: 04-October 09

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 01:57 PM

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.

### #8 aortell24

Reputation: 0
• Posts: 18
• Joined: 07-December 12

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 02:08 PM

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.

### #9 aortell24

Reputation: 0
• Posts: 18
• Joined: 07-December 12

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 05:17 PM

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

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Finding child Nodes of a node in a tree

Posted 31 December 2012 - 06:10 PM

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

### #11 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• Joined: 04-October 09

## Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 12:20 AM

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

### #12 Skydiver

• Code herder

Reputation: 6164
• Posts: 21,263
• Joined: 05-May 12

## Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 12:51 AM

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()
{
:
}
}

```

### #13 Momerath

• D.I.C Lover

Reputation: 1020
• Posts: 2,463
• Joined: 04-October 09

## Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 02:05 AM

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

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Finding child Nodes of a node in a tree

Posted 01 January 2013 - 12:22 PM

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.