# level order traversal of a binary tree without use of queue

• 12-04-2010, 04:08 AM
f1gh
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:
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>)         temp.add(this.root.getData());             //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>)             temp.add(this.root.children.get(i).getData());         }         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               list.add(current.children.get(count).getData());               //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++;             }```

• 12-04-2010, 07:45 PM
f1gh
so nobody knows how to do level order traversal of a binary tree without using a queue??
• 12-06-2010, 05:25 PM
f1gh
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
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.
• 12-06-2010, 05:42 PM
JosAH
Sure you can do it without any auxilliary storage but it's highly inefficient:

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