Thread: level order traversal of a binary tree without use of queue

1. Banned
Join Date
Nov 2010
Posts
44
Rep Power
0

level order traversal of a binary tree without use of queue

Is it possible to do so?
I have this implementation of level order but it doesn't work right as you increase child nodes beyond 0,1,2,3,4 so technically its not level order traversal :confused:
Java Code:
```    public Iterator < T > iterator() {
//temp is a static variable; its a ArrayList<T>();

//root is of type Tree<T>
//its attributes are data,children (List<T>), and parent(Node<T>)

//getNumberOfChildren() returns size of List<Node<T>> children
int num = 0;//this.root.getNumberOfChildren()-1;
for(int i = 0;i<this.root.getNumberOfChildren();i++)
{
//since each child is a Node<T> it also has
//data, children(List<T>), and parent(Node<T>)
}
while(num < this.root.getNumberOfChildren())
{
//this is where the call to levelOrder happens
levelOrder(this.root.children.get(num),temp);
num++;
}

//code for level order
private void levelOrder(Node < T > node, List <T> list) {

Node<T> current = node;

//basically i am finding out how many kids this node has

int count = current.getNumberOfChildren()-1;

//since my getNumberOfChildren returns a junk number if children == null
//my while loop does comparision against that
while(count!=-1 && count > -1)

{
//basically take the data of the child and add it to the list
//if the list still has kids than perform a recursive call on levelOrder
if(current.children.get(count).children!=null){

current = current.children.get(count);

levelOrder(current,list);}

count--;
}

// in my main method i have a statment
//
Tree<Integer> T = new Tree<Integer>();
Iterator levelOrder = T.iterator();
while (levelOrder.hasNext()) {
Integer I = (Integer) levelOrder.next();
if (i > 0) {
System.out.print(", ");
}
System.out.print(I);
i++;
}```

2. Banned
Join Date
Nov 2010
Posts
44
Rep Power
0
so nobody knows how to do level order traversal of a binary tree without using a queue??

3. Banned
Join Date
Nov 2010
Posts
44
Rep Power
0
bump... still interested in finding this out. I have been able to do it with a queue but i want to know if it can be done without usage of a queue or another collection. I have tried manipulating my loops around but it just doesn't seem to quite function right. Works fine for the first 5 nodes in tree
Java Code:
```       0
/   \
1    2
|    |
3    4
/
6```
so if i don't add a child to 3 than the code works fine (one in first post)
as i get 0,1,2,3,4 as traversal output, but with addition of 6 as child of 3 i get
0,1,2,3,6,4 as output, which is not right as it should be 0,1,2,3,4,6
.... with usage of queue i have successfully managed it but i want to know how it can be done w/o queue usage?

keep it mind tree i am not trying to do this as in a traditional tree where you have left and right pointers, this is without those pointers ;) so you don't know if to the right of 0 is 1 and to the left of 0 is 2. ;) all you know is whether each node in tree has children or not, and also does the node have any parent node.

4. Sure you can do it without any auxilliary storage but it's highly inefficient:

Java Code:
```	public boolean traverse(Node root) {

for (int level= 0; traverse(root, level); level++)
}

public boolean traverse(Node node, int level) {
if (level == 0) {
output(node);
return true;
}
else {
boolean hit= false;
for (Node child : node.chidren) {
hit|- traverse(child, level-1);
}
return hit;
}
}```
kind regards,

Jos

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•