Java Recursion and binary tree searching questions

I have updated this thread and added another question

I have to make a binary search tree and then count the occurrences of all the integers in the tree from 1 to size of tree.

The code that I have written to solve this is the following:

public int countOccurrences(int target)
{
int count = 0;
IntBTNode cursor = root;

if(root == null)
return 0;
if(target == root.getData())
return 1;

if (target <= getRoot().getData())
{
while(cursor.getLeft() != null)

{
cursor = cursor.getLeft();
if(target == cursor.getData())
count++;

}
}

if (target > getRoot().getData())
{
while(cursor.getRight() != null)
{
cursor = cursor.getRight();
if(target == cursor.getData())
count++;

}
}

return count;
}

The objective is the get the count of how many times a particular element exists in the tree. My code can find the count of elements in the leftmost children of the left subtree and the rightmost children in the right subtree, but not in the between. Therefore, I don't get to count other elements. Any hints as to how to solve this issue.

Thanks.

There are two cases to code, the base case and the recursive case. The base case happens for n = 1, and is straightforward. For the recursive case, you need to define how row "n" is defined in terms of row "n-1". In other words, if you know how to solve it for "n-1", how can you use that solution for "n"?

Thanks for the post.

I will start building the code:

public static void numbers(int n)
{
if(n == 1)
System.out.println(n);
return;

// now doing the recursive part.....

}

I don't understand this part: row "n" is defined in terms of row "n-1"

What n being defined in terms of n - 1 means is:
Somwehere you have to have a recursive call to numbers(n - 1).

Campbell Ritchie wrote:What n being defined in terms of n - 1 means is:
Somwehere you have to have a recursive call to numbers(n - 1).

so something like this....

public static void numbers(int n)
{
if(n == 1)
System.out.println(n);
return;

// now doing the recursive part.....

numbers(n-1);

}

Now how do I set this up. any hints as to where to start in order to produce the above format of numbers.

numbers(n-1)

This implies that whatever is done for "n-1" is exactly the same as what's being done for "n", but that's not the case. For starters, the output for "n-1" is contained twice in the output for "n", not just once.

And many of us who like structured programming would prefer to see if . . . else rather than if . . . return.

Ulf Dittmer wrote:

numbers(n-1)

This implies that whatever is done for "n-1" is exactly the same as what's being done for "n", but that's not the case. For starters, the output for "n-1" is contained twice in the output for "n", not just once.

Is this what you mean...............

public static void numbers(int n)
{
if(n == 1)
System.out.println(n);

// now doing the recursive part.....

else
n = n*(n-1);

numbers(n-1);

System.out.println(n);

}

I see the output pattern is :

for n = 2;

n-1 n n-1

for n = 3;

n-2 n-1 n-2 n n-2 n-1 n-2.

The problem that I am facing is how to code this pattern mathematically.

Updated thread.

Having a look at your pattern, I see it like this.

n = 1
Output : 1 (Trivial Case)

n = 2
Output : <Output of case n-1> 2 <Output of case n-1>
which turns out to be 1 2 1

n = 3
Output : <Output of case n-1> 3 <Output of case n-1>
which turns out to be <Output of case 2> 3 <Output of case 2>
which is 1 2 1 3 1 2 1

This is the recursion pattern. Of course it's a pretty tough pattern - recursion has never been an easy thing to do.

Sam Mercs wrote:Having a look at your pattern, I see it like this.

n = 1
Output : 1 (Trivial Case)

n = 2
Output : <Output of case n-1> 2 <Output of case n-1>
which turns out to be 1 2 1

n = 3
Output : <Output of case n-1> 3 <Output of case n-1>
which turns out to be <Output of case 2> 3 <Output of case 2>
which is 1 2 1 3 1 2 1

This is the recursion pattern. Of course it's a pretty tough pattern - recursion has never been an easy thing to do.

I understand the pattern as you mentioned. But I cannot think of how to code this in recursive pattern.

This is my first try at recursion and first programming class in Java.

I understand the pattern as you mentioned. But I cannot think of how to code this in recursive pattern. This is my first try at recursion and first programming class in Java.

Have you ever coded anything recursively at all?
If not you should give something a little easier a try first. Maybe these problems might help a bit...

Factorial using recursion -> http://www.javabat.com/prob/p154669
Fibonacci using recursion -> http://www.javabat.com/prob/p120015

Once you get the hang of recursion its pretty easy to write.

Sam Mercs wrote:

I understand the pattern as you mentioned. But I cannot think of how to code this in recursive pattern. This is my first try at recursion and first programming class in Java.

Have you ever coded anything recursively at all?
If not you should give something a little easier a try first. Maybe these problems might help a bit...

Factorial using recursion -> http://www.javabat.com/prob/p154669
Fibonacci using recursion -> http://www.javabat.com/prob/p120015

Once you get the hang of recursion its pretty easy to write.

I am very new to recursion and I have to turn the solution in by beginning of next week. Therefore, I am in sort of a panic mode. We didn't get much time to cover this topic and since its the end of term the course pace has accelerated.

I know I cannot ask for complete solutions but I need some major help here.

I have figured out the recursion problem. I can't believe it. Its almost magical.

But I still need to figure out the counting of elements in the tree.

Ok here some major help, but it's still help.

Lets start with your code,

Now this code is a nice recursion template except that it has nothing to do with your questions, n = n*(n-1) that's not your pattern...

So lets start over with what pattern we need to develop
n = 1
Output : 1 (Trivial Case)

n = 2
Output : <Output of case n-1> 2 <Output of case n-1>
which turns out to be 1 2 1

The first part 'trivial' part of the program is pretty straight,

and then write your main to just call the function above.

So all you need to do is fill in 3 lines of Java code and your done. As I said recursion is simple once you get the hang of it!