12 Replies Latest reply: Jul 30, 2009 1:15 PM by 807588 RSS

    Level order (breadth-first) traversal in a binary-general tree

    807588
      Hi, I have a program that converts a general tree into a binary tree that has nodes of one left child and one right sibling. For an example, a general tree is given like this:
      .
                                             1
                                          /      \
                                       2           6
                                    /    \       /   |   \
                                  3     4     7   8   9
                                         |
                                        5
      and is converted to this:
      .
                                             1
                                          /
                                        2  ----------- 6
                                      /                /
                                    3 ----- 4       7 ------ 8 ----- 9
                                            /
                                          5
      I have a code that performs a level order (breadth first) traversal of the binary tree using a queue, however it is slightly out of order. It is supposed to go 1 -> 2 -> 6 -> 3 -> 4 -> 7 -> 8 -> 9 -> 5, however it instead goes 1 -> 2 -> 6 -> 3 -> 7 -> 4 -> 8 -> 5 -> 9.
      The code is below. If you have any tips on how to fix it, please let me know. Thanks.
      public void printGeneralTree()
          {
              Node rt = root;
              LinkedQueue queue = new LinkedQueue();
      
              if(rt != null)
              {
                  queue.enqueue(rt);
                  while(!queue.isEmpty())
                  {
                      rt = (Node)queue.dequeue();
                      visit(rt);
                      
                      if(rt.right != null)
                          queue.enqueue(rt.right);
                      if(rt.left != null)
                          queue.enqueue(rt.left);
      
                  }
              }
        • 1. Re: Level order (breadth-first) traversal in a binary-general tree
          800427
          Your algorithm is correct, but your tree is painted in a funny way.
          Is 2 and 6 on the same level in the second diagram?
          If this is a binary tree, 6 is one level down and can't be on the same level as 2.
          The same is true for 4.

          So given that the lines between your nodes imply child-parent relationship, your code and output is absolutely correct.
          If you suspect a different output, you can't use a binary tree...
          • 2. Re: Level order (breadth-first) traversal in a binary-general tree
            796440
            jssutton11 wrote:
            Hi, I have a program that converts a general tree into a binary tree that has nodes of one left child and one right sibling.
            Eh? How is that a binary tree? That statement is not even internally consistent. If a node has one sibling, then its parent has two children. But you seem to be saying that any given node can have only one child (which is more a list than a tree).

            >
            .
            1
            /
            2  ----------- 6
            /                /
            3 ----- 4       7 ------ 8 ----- 9
            /
            5
            Yeah, seriously, how is that a binary tree?
            • 3. Re: Level order (breadth-first) traversal in a binary-general tree
              800427
              jverd, if you assume a line means parent->kid, why should this not be a binary tree? It might be unbalanced, still a binary tree datastructure will do just fine creating such a tree.
              If this line connecting nodes means something else, you may be right.
              • 4. Re: Level order (breadth-first) traversal in a binary-general tree
                807588
                It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them.

                The problem is that i have to put out the nodes in the order that I showed you, the odd looking binary tree. 2 and 6 on the same level, and 3 4 7 8 9 on the next level. Does anyone know how I can modify my code to do that?
                • 5. Re: Level order (breadth-first) traversal in a binary-general tree
                  EJP
                  in this layout it has a left child and a right sibling, or one of them.
                  No. The left child has zero or one right siblings. The parent node has one or two children, a left and/or a right.
                  • 6. Re: Level order (breadth-first) traversal in a binary-general tree
                    796440
                    beders wrote:
                    jverd, if you assume a line means parent->kid,
                    I considered that, but it still didn't look right. Maybe I'm just too used to seeing it the normal way. After another look, it seems like it might be okay.
                    If this line connecting nodes means something else, you may be right.
                    He did say something about nodes having a sibling, but at the same time seemed to say that a given parent would only have one child, which is impossible.
                    • 7. Re: Level order (breadth-first) traversal in a binary-general tree
                      796440
                      jssutton11 wrote:
                      It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them.
                      Well, if you want to invent your own terminology to distinguish between a left and right child, and ignore the usual use of sibling, that's your prerogative, but then I'm outta here.
                      • 8. Re: Level order (breadth-first) traversal in a binary-general tree
                        807588
                        jverd wrote:
                        jssutton11 wrote:
                        It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them.
                        Well, if you want to invent your own terminology to distinguish between a left and right child, and ignore the usual use of sibling, that's your prerogative, but then I'm outta here.
                        It's not a different terminology. This code takes a general tree and converts it to a binary tree. The only simple way to do this is to take a parent node, and turn it's multiple children into one leftmost child, and that child will have a right sibling, and that right sibling will also have a right sibling. Again, for example:
                        .
                                          1 
                                      /   |   \
                                    2     3     4
                        converts to
                        .
                                          1
                                        /
                                      2  -- 3 -- 4
                        Hopefully that clears things up. If anyone still has some constructive advice, I'd greatly appreciate it. Thanks.
                        • 9. Re: Level order (breadth-first) traversal in a binary-general tree
                          796440
                          jssutton11 wrote:
                          jverd wrote:
                          jssutton11 wrote:
                          It is a binary tree because each node is only linked to two other nodes, which would normally be called the children, but in this layout it has a left child and a right sibling, or one of them.
                          Well, if you want to invent your own terminology to distinguish between a left and right child, and ignore the usual use of sibling, that's your prerogative, but then I'm outta here.
                          It's not a different terminology. This code takes a general tree and converts it to a binary tree. The only simple way to do this is to take a parent node, and turn it's multiple children into one leftmost child, and that child will have a right sibling,
                          This is where you're inventing your own terminology. If a node has a sibling, then those two nodes have the same parent, and that parent has both of those nodes as children. So you've redefined one or more of sibling, parent, child, and, as a consequence, you're now also redefining binary tree.

                          Edited by: jverd on Jul 30, 2009 10:09 AM
                          • 10. Re: Level order (breadth-first) traversal in a binary-general tree
                            796440
                            ejp wrote:
                            in this layout it has a left child and a right sibling, or one of them.
                            No. The left child has zero or one right siblings. The parent node has one or two children, a left and/or a right.
                            And, following along, the right child also has zero or one left siblings, and both siblings share the same parent, and that parent's children are those siblings.
                            • 11. Re: Level order (breadth-first) traversal in a binary-general tree
                              807588
                              The terminology makes sense in the context of the first (non-binary) tree. The second tree has its own left/right children, but they represent leftmost child and right sibling from the first tree.

                              Instead of enqueuing just rt.right, you need to enqueue all of the node's siblings before enqueuing rt.left. This would be easier if you knew whether a node was the leftmost child and only enqueing its siblings in that case.

                              It could help if you posted most code including the creation of a sample tree
                              • 12. Re: Level order (breadth-first) traversal in a binary-general tree
                                807588
                                fgb wrote:

                                Instead of enqueuing just rt.right, you need to enqueue all of the node's siblings before enqueuing rt.left. This would be easier if you knew whether a node was the leftmost child and only enqueing its siblings in that case.
                                Thanks, that actually did it right there, I should have realized that.

                                The modified code is this, for anyone interested:
                                if(rt != null)
                                        {
                                            queue.enqueue(rt);
                                            while(!queue.isEmpty())
                                            {
                                                rt = (Node)queue.dequeue();
                                                left = rt.left;
                                                
                                                if(left != null && left.right != null)
                                                    right = left.right;
                                                else
                                                    right = null;
                                                
                                                visit(rt);
                                                
                                                if(left != null)
                                                {
                                                    queue.enqueue(left);
                                                    while(right != null)
                                                    {
                                                        queue.enqueue(right);
                                                        if(right.right != null)
                                                            right = right.right;
                                                        else
                                                            right = null;
                                                    }
                                                }
                                            }
                                        }