Recursively counting specific nodes in a binary search tree

Question

I'm trying to create a method in Java to count Nodes in a Binary Search Tree that contain a certain value and print out their contents. Each Node contains an Article object which has a title, and I want to find and print Articles in the tree containing a keyword in the title. However, I don't want the program to print out more than 10 of these (a 1-letter keyword could cause the program to stall or crash, for example). The code is here:

    public int traverse(String key) {
    if (root == null) {
        System.out.println("Empty Tree!");
        return 0;
    } else {
        int n = traverseHelper(root, key, 0);
        return n;
    }
}

public int traverseHelper(Node t, String key, int n) {
    if (t == null) {
        return n;
    } else {
        if (t.data.getTitle().indexOf(key) >= 0 && n <= 10) {
            System.out.println(t.data);
            n++;
        }
        return traverseHelper(t.left, key, n) + traverseHelper(t.right, key, n);
    }
}

I'm trying to keep a running count of how many times the program has printed the data, but I'm not entirely sure how. Currently the program prints all occurrences, or very close to it. I know something is wrong with my recursive approach (I'm never any good at recursion anyway), so a good explanation of what I'm doing wrong would be greatly appreciated. This is homework, though, so I don't expect an explicit solution. A couple other things: the traverse function's purpose is to print out the Articles, so I will most likely change it to a void method later. It currently should return the final count of articles printed. Also, the tree is set up like any other BST, but I'll give any clarification of my code if necessary.

Thanks!

Answer 1

Since you count with n you can only pass n to one of the leafs or you can nest them like this:

public int traverseHelper(Node t, String key, int n) {
    if (t == null) {
        return n;
    } else {
        if (t.data.getTitle().indexOf(key) >= 0 && n <= 10) {
            System.out.println(t.data);
            n++;
        }
        return traverseHelper(t.left, key, traverseHelper(t.right, key, n));
    }
}

Nesting like this reduces stack usage slightly since you don't have the extra adding and the left becomes a tail call. Java don't have tail call optimization but it doesn't hurt to write as if it had.

Answer 2

The issue I see is with the n variable.

You do

return traverseHelper(t.left, key, n) + traverseHelper(t.right, key, n);

So if n was 5 to begin with, your method would return 10 (5 from each branch) even if no items were found.

Make the function return only the number of items found in the subtree.