CODEWITHSUNDEEP
javarecursiontree
Snowman
Snowman

Reputation: 32071

Help with tree recursion

I have a Person class, and I want to create a tree. Here is the contsructor for the Person class. 

public Person(String name, int age, char gender, Person c1, Person c2)

c1 is the child on the left, and c2 is the child on the right. And so say I create three Persons like so:

Person c = new Person("Carl", 50, 'M', null, f);

Person b = new Person("Barbara", 52, 'F', d, e);

Person a = new Person("Adam", 75, 'M', b, c);

So here you say Adam is the root node, and Adam's left child is b, which is Barbara and his right c which is Carl, and so on.

So what I want to do is write a count method, that counts the number of children including this. So a.count() would return 6 (if Person f doesnt have any children).

And so here's the code I have:

public int count() // total person count including this object
{
    if(child1==null)
        return 0; //I tried return 1 for this too didnt work
    if (child2==null)
        return 0; //also tried 1 for this
    return 1+this.child1.count() +1+this.child2.count();
}

I ran this on paper several times, and it should come up with the correct result, but it's off by a few for some reason when I actually run it.

Upvotes: 2

Views: 1165

Answers (3)

Jack
Jack

Reputation: 133577

The result is wrong because you return 0 when a child is null forgetting to count the node itself or the other child.. if it's a leaf node (child1 == null && child2 == null) you should anyway return 1.

Something like:

return 1 + (child1 == null ? 0 : child1.count()) + (child2 == null ? 0 : child2.count())

following your original code it would be something like:

if (child1 == null && child2 == null)
  return 1;
else if (child1 == null)
  return 1 + child2.count();
else if (child2 == null)
  return 1 + child1.count();
else
  return 1 + child1.count() + child2.count();

but in that case I would say to stick with jjnguy answer which calculates the result partially..

Upvotes: 4

jjnguy
jjnguy

Reputation: 138884

Your code returns 0 if one of the children are null. This is incorrect because you don't account for the other child, or this. The count should always be >= 1 because you always have at least one node in the tree.

Also, you can't return right away if you see that one child is null. You need to count the other child too (if it exists).

Here is how I would implement it:

public int count() // total person count including this object
{
    int count = 1; // we count this node as 1 
    if (child1 != null) // if we have a left child, count its size
        count += child1.count();
    if (child2 != null) // if we have a right child, count its size
        count += child2.count()
    return count;
}

You need to account for both children, even if one of them is null.

Upvotes: 4

Lavir the Whiolet
Lavir the Whiolet

Reputation: 1016

private int count() {
    return 1 + ((this.child1 != null) ? (this.child1.count()) : (0)) + ((this.child2 != null) ? (this.child2.count()) : (0));
}

Upvotes: 0

Related Questions