This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Java Recursion  and binary tree searching questions Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Java Recursion  and binary tree searching questions" Watch "Java Recursion  and binary tree searching questions" New topic
Author

Java Recursion and binary tree searching questions

Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41065
    
  43
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"?


Ping & DNS - my free Android networking tools app
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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"
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37926
    
  22
What n being defined in terms of n - 1 means is:
Somwehere you have to have a recursive call to numbers(n - 1).
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41065
    
  43
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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37926
    
  22
And many of us who like structured programming would prefer to see if . . . else rather than if . . . return.
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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);

}
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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.
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
Updated thread.
Saifuddin Merchant
Ranch Hand

Joined: Feb 08, 2009
Posts: 597

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.



Cheers - Sam.
Twisters - The new age Java Quiz || My Blog
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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.
Saifuddin Merchant
Ranch Hand

Joined: Feb 08, 2009
Posts: 597

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.
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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.
Dubravko Zubavich
Greenhorn

Joined: Mar 04, 2009
Posts: 20
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.
Saifuddin Merchant
Ranch Hand

Joined: Feb 08, 2009
Posts: 597

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!
 
 
subject: Java Recursion and binary tree searching questions
 
Similar Threads
BST problem (Online waiting)
Implement methods for Iterator using Generics for TreeSet
recursive method to balance a binary tree
Draw binary tree structure
Please critique my countOccurrence method for IntTreeBag class