Home > Software design >  Level Order Binary Tree Traversal (upton n level) in C#
Level Order Binary Tree Traversal (upton n level) in C#

Time:12-06

I'm trying to understand level order traversal of a tree using a queue. Here is my code (https://www.geeksforgeeks.org/level-order-tree-traversal/):

    void printLevelOrder()
    {
        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(root);
        while (queue.Count != 0) { 

            Node tempNode = queue.Dequeue();
            Console.Write(tempNode.data   " "); 
            
            if (tempNode.left != null) {
                queue.Enqueue(tempNode.left);
            } 
            
            if (tempNode.right != null) {
                queue.Enqueue(tempNode.right);
            }
        }
      }

How do I print nodes in a tree upto level n using a queue?

eg:

                    1    ------------------- Level 1
                 2     3 ------------------- Level 2
              5    6  7  8 ----------------- Level 3
             4  11        ------------------ Level 4

print nodes upto level 3?

CodePudding user response:

Associate each node with its level:

void printLevelOrder(int maxLevel)
    {
        var queue = new Queue<(Node node, int Level)>();
        queue.Enqueue(root);
        while (queue.Count != 0) { 

            var (tempNode, level) = queue.Dequeue();
            if(level > maxLevel) return;
            Console.Write(tempNode.data   " "); 

            
            if (tempNode.left != null) {
                queue.Enqueue((tempNode.left, level 1));
            } 
            
            if (tempNode.right != null) {
                queue.Enqueue((tempNode.right, level 1));
            }
        }
      }

CodePudding user response:

If you want to print elements level-by-level you have to add one more extra constraint, before putting each element on queue; you need to check size of queue so that you can only dequeued i-th element at a time where i is the size of the queue and only enqueued each sub-trees i-th elements.

 void printLevelOrder(){
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(root);
    while (queue.Count != 0) { 
        int size = queue.getSize();
        list Array/LinkedList;
        while(size-- > 0){
           Node tempNode = queue.Dequeue();
           list.add(tempNode.data);

           if (tempNode.left != null) {
              queue.Enqueue(tempNode.left);
           } 
        
            if (tempNode.right != null) {
              queue.Enqueue(tempNode.right);
            }
        }
        print: list;
    }
  } 

Note: please ignore syntax-error, and try to make the code in C#.

  • Related