CODEWITHSUNDEEP
javarecursionbinary-search-tree
reCursed
reCursed

Reputation: 165

Conditionally counting nodes in a tree traversal - recursively

Working on a University assignment which requires comparing nodes in a tree and making a count of nodes which meet a certain condition. I can see how I could do this iteratively, traversing the tree with a stack etc, but I'm certain the lecturers are looking for a recursive solution and I'm struggling to wrap my head around this particular implementation.

My current (flawed) implementation is:

public int traverseIncrement(User user, User reference) {

    if(user == null)
        return 0;

    int count = 1;

    if (user.getLeft() != null) {
        if(user.getLevel() > reference.getLevel()) {
            count += traverseIncrement(user.getLeft(), reference);
        }
    }

    if (user.getRight() != null) {
        if(user.getLevel() > reference.getLevel()) {
            count += traverseIncrement(user.getRight(), reference);
        }
    }

    return count;       
}

There are two obvious problems, the first being that the first node is never evaluated and the second being that I am always one higher than the required output. Any nudge in the right direction would be helpful!

Upvotes: 0

Views: 530

Answers (1)

lurker
lurker

Reputation: 58244

I think the two problems are related. Rather than assume the count is 1 then recurse depending upon whether the condition is met, you should set count depending upon the condition, then recurse. In other words, leave the evaluation of a given node up to the call that is handling that node.

Also, you can eliminate the check for left or right being null since your function already checks on entry.

public int traverseIncrement(User user, User reference) {
    if(user == null)
        return 0;

    int count = (user.GetLevel() > reference.getLevel()) ? 1 : 0;

    count += traverseIncrement(user.getLeft(), reference);
    count += traverseIncrement(user.getRight(), reference);

    return count;
}

Upvotes: 1

Related Questions