• Post Reply Bookmark Topic Watch Topic
  • New Topic

output the levelOrder traversal of a Binary search tree  RSS feed

 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i am trying to output the levelOrder traversal of a Binary search tree. but the execution doesnt seem to run past the input stage; any help or insight will be appreciated.

the code doesnt print an error, but did not break out of the input stage where it is supposed to receive input of lenght T and process it in the BINARY SEACH tree.
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you copy the contents of the console from the execution and paste it here?

Add some comments describing what you expect the output to look like.

Note: A for statement is better for a loop when the number of iterations is known before the loop starts execution.
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To see why the while loop is not working, add a print statement inside the loop that prints the value of T.
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:Can you copy the contents of the console from the execution and paste it here?

Add some comments describing what you expect the output to look like.

Note: A for statement is better for a loop when the number of iterations is known before the loop starts execution.


The output is just is to be the values in the queue arranged in a LevelOrder traversal format. That's why I read the queue into an array and print it out with toString() method
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
how are you trying to debug the code?
Did you add the print statement I suggested to see what the value of T was as the loop executed?

Add some more print statements that print the values of variables as the program executes so you can see what the code is doing.
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I decide to change the while(queue != Null) to while(!(queue.isEmpty()).
And after adding print statements this is my code



class NodeT {

NodeT left, right;

int data;

NodeT(int data) {

this.data = data;

left = right = null;

}

}

public class Bst {

static String levelOrder(NodeT root) {

// Write your code here

LinkedList<NodeT> queue = new LinkedList<>();

int [] array = new int [queue.size()];

if (root == null) {

return array.toString();

} else if (root != null) {

// enqueue the current root

queue.addFirst(root);

// while there are nodes to process

while (!(queue.isEmpty())) {

// dequeue next node

NodeT tree = (NodeT) queue.removeFirst();

queue.addFirst(tree);
System.out.println(  "add first node");

// enqueue child element from next level inOrder

if (tree.left != null) {

queue.add(tree.left);
System.out.println(  "add left node");
}

if (tree.right != null) {

queue.add(tree.right);
System.out.println(  "add right node");
}

}

for(int i= 0; i< array.length; i++) {

array[i] = queue.remove().data;

}

}

  

return array.toString();}

public static NodeT insert(NodeT root, int data) {

if (root == null) {

return new NodeT(data);

} else {

NodeT cur;

if (data <= root.data) {

cur = insert(root.left, data);

root.left = cur;

} else {

cur = insert(root.right, data);

root.right = cur;

}

return root;

}

}

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);

int T = sc.nextInt();

NodeT root = null;

while (T-- > 0) {

int data = sc.nextInt();

root = insert(root, data);

}

levelOrder(root);

}

}


The output was that , the while loop do run but , it enters an infinite loops that print the two first print statement that I added alternatingly, without reaching the third print statement.

 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please wrap all posted code in code tags to preserve formatting and make it easier to read.

What problems or questions do you have now?

How are you trying to debug the code?
Did you add the print statement I suggested to see what the value of T was as the loop executed?
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i edited it and use

but the output of this is an infinite loop that prints the output repeatedly without reaching the next statement
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the output of this is an infinite loop that prints the output repeatedly


Can you copy some of the output and paste it here so we can see what it being output.

I don't see the print statement I suggested:  to see what the value of T was as the while loop executed
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:
the output of this is an infinite loop that prints the output repeatedly


Can you copy some of the output and paste it here so we can see what it being output.

I don't see the print statement I suggested:  to see what the value of T was as the while loop executed



this is the recent edit with the value of Data.



and a little portion of the output, which is an infinite loop that doesnt break out of the while Loop

 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
n infinite loop that doesnt break out of the while Loop

I don't understand why you are refusing to add the print statement that I suggested to print the value of T inside of the while loop.  The print out will show you why there is an infinite loop.

Did you write all of this code
OR
Did your instructor give you this program with bugs and you are supposed to find and fix them?
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maybe I don't understand your point , when you said I should add the print statement that print T, because as I see it, T is just a counter variable that keep track of the amount of input that enters the tree. And that can be any number. In running the code the first inputstream prompt was to enter the value for T , which I choose 6(in other to make the tree full and more than 1 level), and as I enter number into the tree; T will serve as the counter variable that makes sure I don't input more than the 6 input I specified. So , when you asked me to print T, I think you are referring to the value of the variable: 'Data' and not T; and that is why I printed the output you saw in the last edit.

If you can explain more on what you mean by printing T, maybe that can clear up the air. Thanks for your help so far...


I wrote the code myself on a different topic on Binary search tree, and was later given an assignment  to include a method That prints the LevelOrder traversal of the tree.
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
when you asked me to print T, I think you are referring to the value of the variable: 'Data' and not T;

No, I was and am referring to the variable T.  Why do you continue to refuse to print its value?  The print out will show you why the loop is infinite.

You are assuming you know what the code is doing.  But it isn't doing what you want. There is a bug.  Print T to see what the code is doing.
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:
when you asked me to print T, I think you are referring to the value of the variable: 'Data' and not T;

No, I was and am referring to the variable T.  Why do you continue to refuse to print its value?  The print out will show you why the loop is infinite.

You are assuming you know what the code is doing.  But it isn't doing what you want. There is a bug.  Print T to see what the code is doing.


The value is 6, and it determine the length of the numbers passed into the 🌲 tree. Let me illustrate how the input will go , immediately the code is compiled:

The first input is T
"Input the value of T"
6
" Input T nos of values to fill the tree"
6
8
9
2
5
7
1
Note: T = 6, and it is the length of the numbers inputed into the tree.
I hope you get my point.
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
adebari olalekan wrote:
Norm Radder wrote:
when you asked me to print T, I think you are referring to the value of the variable: 'Data' and not T;

No, I was and am referring to the variable T.  Why do you continue to refuse to print its value?  The print out will show you why the loop is infinite.

You are assuming you know what the code is doing.  But it isn't doing what you want. There is a bug.  Print T to see what the code is doing.


The value is 6, and it determine the length of the numbers passed into the 🌲 tree. Let me illustrate how the input will go , immediately the code is compiled:

The value is 6, and it determine the length of the numbers passed into the 🌲 tree. Let me illustrate how the input will go , immediately the code is compiled:

The first input is T
"Input the value of T"
6
" Input T nos of values to fill the tree"
8
9
2
5
7
1
Note: T = 6, and it is the length of the numbers inputed into the tree.
I hope you get my point.
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Which of the printed numbers are the value of T inside of the loop?  The print out does not show which numbers are the value of T.

Make use to have an id String when printing out numbers so you can tell which is which.  Something like this:
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To Simply put it;

T = 6
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To Simply put it;

T = 6

If it only prints one time, then the loop is not looping.  There should be many print outs for while the code is looping.

What is printed when the print statement is INSIDE the while loop?
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
adebari olalekan wrote:
Norm Radder wrote:
the output of this is an infinite loop that prints the output repeatedly


Can you copy some of the output and paste it here so we can see what it being output.

I don't see the print statement I suggested:  to see what the value of T was as the while loop executed



this is the recent edit with the value of Data.



and a little portion of the output, which is an infinite loop that doesnt break out of the while Loop



This is what is printed when the print statement is inside the loop.

Please Note: T cannot be printed inside the while loop, please re-read the code again, the scope of the variable T is only bounded in the main method , and does not reach the levelOrder() method.
 
Norm Radder
Rancher
Posts: 2240
28
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wow. I had a hole in what I thought happened.  I didn't remember that shortcut permanently changed the value of a variable.  Probably because it was in a while loop instead of in a for loop???
I was thinking it was like the expression: (T - 1) - returned the value but left T unchanged.


Ok time to move into debugging the code in the levelOrder() method.
A useful techique for debugging linked lists is to add a toString() method to the Node class that returns data, left and right for the Node.  Then printing the contents of the List will show its structure as the code is executed.

When will the condition in the while statement on line 24 ever be false?


T cannot be printed inside the while loop

Did you try it?  What happened?  It works on my PC.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A small hint:

If you look at this code:

can you see why you end up in an infinite loop?
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:A small hint:

If you look at this code:

can you see why you end up in an infinite loop?


Yes, I guess the code is not breaking out of the while loop, because the queue is not completely empty; so, the isEmpty() method continue returning false. That is the problem I am having, how to break out of that infinite loop, any suggestions?.

On the side Note, can you explain more on the reason why it is in that infinite state. I don't seem to understand it to the root.
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
how to break out of that infinite loop, any suggestions?. 

What is the loop supposed to do?
When should the loop end?
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, the intention is to print the Tree, but first the head, then the two nodes beneath (i.e. head.left and head.right), then the (possibly) 4 nodes on level 2, et cetera.

There is nothing wrong with the algorithm that OP uses, it is just that the head of the queue is removed (which is as it should be), then added immediately as head again to the queue. Therefore, the head never changes, its left and right nodes are added to the queue ad infinitum, and the process never ends. So, remove the head, do something  with it, and only add its left and right nodes to the queue.

Once passed this hurdle, you will notice another error, but that for later.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!