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

    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>)
           //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>)
            while(num < this.root.getNumberOfChildren())
           //this is where the call to levelOrder happens
    //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
                   //if the list still has kids than perform a recursive call on levelOrder
                       current = current.children.get(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);
    			if (i > 0) {
    				System.out.print(", ");

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

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


    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
    Rep Power


    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:
         /   \
        1    2
        |    |
        3    4
    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 offline Moderator
    Join Date
    Sep 2008
    Voorschoten, the Netherlands
    Blog Entries
    Rep Power


    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) {
    			return true;
    		else {
    			boolean hit= false;
    			for (Node child : node.chidren) {
    				hit|- traverse(child, level-1);
    			return hit;
    kind regards,

    Build a wall around Donald Trump; I'll pay for it.

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, 03:45 AM
  3. Replies: 0
    Last Post: 04-04-2010, 08:40 AM
  4. Level order binary tree traversal
    By H3rtaherta in forum New To Java
    Replies: 1
    Last Post: 04-20-2009, 08: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