Level Order Linewise Traversal

FAQ

1. Can we use any other data structure despite queue to travel linewise?
Answer: Yes we can use stack also. But we have to use 2 stacks for it.

2. Can we travel linewise just with a single queue?
Answer: Yes we can but, we have to use 2 while loops for that .

3. Can we use recursion to tarvel linewise in tree?
Answer: Yes we can but we have to use extra parameters for levels.

4. Can we use hashmap functionality  to travel linewise?
Answer: Yes we can assign keys for different levels and store the values of childrens in levels and do so.

Hint

1. Can we use Remove-Print-Add algorithm here ?
2. Use 2 queue: main and child queue
3. Start from root node and print it then remove it from initial queue i.e. main queue 
4. Add all the children of this node into child queue and repeat Remove-Print-Add algo untill both the queue becoms empty.
5. Also, in between the procedure, whenever the main queue becomes empty we will leave a line and we will copy all the contents of the child queue to the main queue and make the child queue  empty. 

MCQ

1. Level order traversal of a tree is formed with the help of
  a. breadth first search
  b. depth first search
  c. dijkstra’s algorithm
  d. prims algorithm
  
Answer: a. breadth first search

2. What is the time complexity of level order traversal?
  a) O(1)
  b) O(n)
  c) O(logn)
  d) O(nlogn)
  
Answer: b) O(n)

3.  Which of the following graph traversals closely imitates level order traversal of a binary tree?
  a) Depth First Search
  b) Breadth First Search
  c) Depth & Breadth First Search
  d) Binary Search
 
 Answer: b) Breadth First Search
 
 4. What is the space complexity of level order linewise traversal in a tree?
  a) O(1)
  b) O(n)
  c) O(logn)
  d) O(nlogn)
  
Answer: b) O(n)