Results 1 to 4 of 4
  1. #1
    f1gh is offline Member
    Join Date
    Nov 2010
    Posts
    46
    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 Member
    Join Date
    Nov 2010
    Posts
    46
    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 Member
    Join Date
    Nov 2010
    Posts
    46
    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
    13,518
    Blog Entries
    7
    Rep Power
    20

    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. need help with post order traversal
    By Metastar in forum New To Java
    Replies: 3
    Last Post: 11-08-2010, 08: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, 12: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
  •