# Java Recursion and binary tree searching questions

Dubravko Zubavich

Greenhorn

Posts: 20

posted 7 years ago

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.

**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

Rancher

Posts: 42967

73

posted 7 years ago

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"?

Dubravko Zubavich

Greenhorn

Posts: 20

Campbell Ritchie

Sheriff

Posts: 48652

56

Dubravko Zubavich

Greenhorn

Posts: 20

posted 7 years ago

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.

Campbell Ritchie wrote:Whatnbeing defined in terms ofn- 1 means is:

Somwehere you have to have a recursive call tonumbers(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

Rancher

Posts: 42967

73

Campbell Ritchie

Sheriff

Posts: 48652

56

Dubravko Zubavich

Greenhorn

Posts: 20

posted 7 years ago

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);

}

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

Posts: 20

posted 7 years ago

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.

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.

posted 7 years ago

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

which is

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

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

Posts: 20

posted 7 years ago

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.

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 is1 2 131 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.

posted 7 years ago

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 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.

Cheers - Sam.

Twisters - The new age Java Quiz || My Blog

Dubravko Zubavich

Greenhorn

Posts: 20

posted 7 years ago

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.

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

Posts: 20

posted 7 years ago

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!

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!

Cheers - Sam.

Twisters - The new age Java Quiz || My Blog

Consider Paul's rocket mass heater. |