10 Replies Latest reply on Mar 18, 2007 3:29 PM by JosAH

# Binary tree per levels

I must make a method that takes the variable "item" and put it in a string, for each element of the binary tree, but per levels..for example:
``````              1
2     3               6
5                                4``````
must return this string: 1 , 2 , 3 , 6 , 5 , 4

The tree is something like:
``````public class BinTree{
private Node root;

public class Node{
public Node left;
public Node right;
public int item;
}
}``````
Thank you very much :)
• ###### 1. Re: Binary tree per levels
...
Thank you very much :)
For what?
• ###### 2. Re: Binary tree per levels
Sorry, I didn't specify: I can use recursion, but in this case I don't know how to do it "per levels"..can someone help me? Also if you don't write the method, just to tell me how to go through the tree in this case. Thanks
• ###### 3. Re: Binary tree per levels
Sorry, I didn't specify: I can use recursion,
Level order traversals are normally performed using a queue.

but in this case I don't know how to do it "per levels"..can
someone help me?
Sure: use a queue and try to do it first on a pice of paper.

Also if you don't write the method,
I won't. ; )
What would you learn from that? Perhaps a little, but you'll learn far more by doing it yourself.

just to tell me how to go through the tree in this
case. Thanks
Here's some pseudo code:
```LEVELORDER(root)
queue.enqueue(root)
WHILE queue not empty
n = queue.dequeue()
IF n.left  != null -> queue.enqueue(n.left )
IF n.right != null -> queue.enqueue(n.right)
END WHILE
END LEVELORDER```
And an example. Take the following tree:
```     5
/ \
/   \
3     8
/ \   / \
1   4 6   9```
No apply that pseudo code:
```queue = new queue
queue.enqueue(5)

while(queue is not empty) {

n = queue.dequeue() = 5
n.left  != null, so queue.enqueue(3)
n.irght != null, so queue.enqueue(8)
(queue is now [3,8])

n = queue.dequeue() = 3
n.left  != null, so queue.enqueue(1)
n.irght != null, so queue.enqueue(4)
(queue is now [8,1,4])

n = queue.dequeue() = 8
n.left  != null, so queue.enqueue(6)
n.irght != null, so queue.enqueue(9)
(queue is now [1,4,6,9])

n = queue.dequeue() = 1
n.left  == null
n.irght == null
(queue is now [4,6,9])

n = queue.dequeue() = 4
n.left  == null
n.irght == null
(queue is now [6,9])

n = queue.dequeue() = 6
n.left  == null
n.irght == null
(queue is now [9])

n = queue.dequeue() = 9
n.left  == null
n.irght == null
(queue is now [])

queue is empty, end while.
}```
As you can see, the items are dequeued in the following order: 5, 3, 8, 1, 4, 6, 9.
Good luck.
• ###### 4. Re: Binary tree per levels
I didn't know anything about the class "Queue"...
I don't understand why if I write "Queue queue = new Queue();" I obtain the error "queue is abstract cannot be instantiated"...so I can't make operations like queue.dequeue() !
I searched in Internet but I didn't understand what happens. Can someone help me, please?

Thanks prometheuzz for your big help!

Message was edited by:
-Marco-
• ###### 5. Re: Binary tree per levels
A java.util.Queue is an interface:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html
so, you cannot instantiate it like this:
``Queue queue = new Queue();``
and a java.util.LinkedList is an implementation of that interface:

So, what you can do is this:
``````import java.util.Queue;

// ...

yourMethod() {
// ...
}``````
Now you can call all methods defined in the Queue interface on your queue reference.
Note that the Queue interface does not have enqueue(...) and dequeue() methods but offer(...) and poll().

Good luck.
• ###### 6. Re: Binary tree per levels
I've written this:
``````
public String toString(Node root){

if (root== null)
return "";  // There is nothing to print in an empty tree.

queue.offer(root);
while ( queue.isEmpty() == false ) {
node = (Node)queue.poll();
System.out.println( node.label );
if ( node.left != null )              queue.offer( node.left );
if ( node.right != null )           queue.offer( node.right );
}

return "";
}``````
I'll put the memorization in the string when I'll make this part work...
I've 2 problems:
1) I used a casting operation to transform the queue.poll() result in a BinNode type, do you think it should work?
2) I receive the error: "MyTree.java uses unchecked or unsafe operations"..which unsafe operation have I used?

Message was edited by:
-Marco-
• ###### 7. Re: Binary tree per levels
I've 2 problems:
1) I used a casting operation to transform the queue.poll() result in a
BinNode type, do you think it should work?
2) I receive the error: "MyTree.java uses unchecked or unsafe
operations"..which unsafe operation have I used?
A bit of generics sprinkled in never hurt:
``````Queue<Node> queue= new LinkedList(Node);
...
node= queue.poll(); // no cast needed anymore``````
kind regards,

Jos
• ###### 8. Re: Binary tree per levels
Great, it's working now ^^
I?m sorry but I thought that the <> were just to show some parameters...I didn't know it was an instruction! Now I'm going to study this thing, thanks again :)
• ###### 9. Re: Binary tree per levels
Of course I made a few typos again; I wanted to type this:
``Queue<Node> queue= new LinkedList<Node>();``
kind regards,

Jos
• ###### 10. Re: Binary tree per levels
I?m sorry but I thought that the <> were just to show
some parameters...
Those things between the angular brackets are parameters; they're
type parameters to be more exact. Read all about it in the generics