level order traversal of a binary tree without use of queue

[f1gh]

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:

    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++;
    	}

any suggestions, helpful comments elaborating level order traversal would be appreciated.

[f1gh]

so nobody knows how to do level order traversal of a binary tree without using a queue??

[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

       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.

[JosAH]

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

	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