Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Level Order Traversal, Print each level in separate line.

Objec­tive: Given a Binary tree , Print each level of a tree in sep­a­rate line.

NOTE : This prob­lem is very sim­i­lar ” Cre­ate Linked Lists of all the nodes at each depth ”

Input: A binary tree

Out­put: Each level of binary tree, in one line

Exam­ple:

Level Order Traversal, Print each level in one line.

Level Order Tra­ver­sal, Print each level in one line.

Approach:

Naive Approach:

  1. Get the height of the tree.
  2. Put a for loop for each level in tree.
  3. for each level in step 2, do pre order tra­ver­sal and print only when height matches to the level.
  4. Look at the code for bet­ter explanation

Time Com­plex­ity : O(N^2) — because each level you are tra­vers­ing the entire tree.

Bet­ter Solu­tion :   Time Com­plex­ity — O(N)

  • Cre­ate a ArrayList of Linked List Nodes.
  • Do the level order tra­ver­sal using queue(Breadth First Search). Click here to know about how to level order tra­ver­sal.
  • For get­ting all the nodes at each level, before you take out a node from queue, store the size of the queue in a vari­able, say you call it as levelNodes.
  • Now while levelNodes>0, take out the nodes and print it and add their chil­dren into the queue.
  • After this while loop put a line break.
while(!q.isEmpty()){
	levelNodes = q.size();
	while(levelNodes>0){
		Node n = (Node)q.remove();
		System.out.print(" " + n.data);
		if(n.left!=null) q.add(n.left);
		if(n.right!=null) q.add(n.right);
		levelNodes--;
	}
	System.out.println("");
}

  • Since we had taken the queue size before we add new nodes, we will get the count at each level and after print­ing this count, put a line break, see the exam­ple below
Level Order Traversal, Print each level in separate line.

Level Order Tra­ver­sal, Print each level in sep­a­rate line.

Com­plete Code:


Out­put:

Output by Naive Approach :
5
10 15
20 25 30 35
Output by Better Approach :
5
10 15
20 25 30 35

You may also like...

  • http://abhis.ws Abhishek

    Or you can take two coun­ters, cur­rent and next level. Keep print­ing on the same line till cur­rent reaches 0. at that point you have com­pleted a level. make current=next, next=0 and print a line break. this will avoid a sec­ond loop.

    • Sumit

      Did you try imple­ment­ing it? what val­ues will you store in coun­ters and more impor­tantly how will you know that you have reached to the last node at par­tic­u­lar level?? you will need an iden­ti­fier to insert in queue to know about the level change.

      • http://abhis.ws Abhishek

        https://gist.github.com/adeydas/d209dca13927fb8a63fd — I checked with only the input in this posts, so feel free to check some more.

        • Sumit

          Thanks for the link. I have checked the code. Both has the same com­plex­ity, what you have said is right. the code will iter­ate the same num­ber of time.

  • Akash G

    what is the time com­plex­ity of the bet­ter solution?

    • tuto­ri­al­hori­zon

      We are vis­it­ing each node only once , so it will be O(N)