Results 1 to 4 of 4
  1. #1
    f1gh is offline Banned
    Join Date
    Nov 2010
    Posts
    44
    Rep Power
    0

    Default 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.

  2. #2
    f1gh is offline Banned
    Join Date
    Nov 2010
    Posts
    44
    Rep Power
    0

    Default

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

  3. #3
    f1gh is offline Banned
    Join Date
    Nov 2010
    Posts
    44
    Rep Power
    0

    Default

    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. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,048
    Blog Entries
    7
    Rep Power
    23

    Default

    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
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. need help with post order traversal
    By Metastar in forum New To Java
    Replies: 3
    Last Post: 11-08-2010, 09:40 PM
  2. binary tree
    By ryamz in forum New To Java
    Replies: 2
    Last Post: 08-12-2010, 02:45 AM
  3. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  4. Level order binary tree traversal
    By H3rtaherta in forum New To Java
    Replies: 1
    Last Post: 04-20-2009, 07:34 AM
  5. Binary Search Tree Traversal
    By dch414 in forum New To Java
    Replies: 2
    Last Post: 11-07-2008, 01:01 AM

Posting Permissions

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