Results 1 to 4 of 4
 12042010, 04:08 AM #1Banned
 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>) 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.
 12042010, 07:45 PM #2Banned
 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??
 12062010, 05:25 PM #3Banned
 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
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.
 12062010, 05:42 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 29
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, level1); } return hit; } }
JosBuild a wall around Donald Trump; I'll pay for it.
Similar Threads

need help with post order traversal
By Metastar in forum New To JavaReplies: 3Last Post: 11082010, 09:40 PM 
binary tree
By ryamz in forum New To JavaReplies: 2Last Post: 08122010, 03:45 AM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 08:40 AM 
Level order binary tree traversal
By H3rtaherta in forum New To JavaReplies: 1Last Post: 04202009, 08:34 AM 
Binary Search Tree Traversal
By dch414 in forum New To JavaReplies: 2Last Post: 11072008, 01:01 AM
Bookmarks