In this tutorial, we will see the Level Order Traversal of a Binary Tree using Queue. This method of traversal is Iterative Method.
Algorithm for levelOrder()method:
public void levelOrder(Node node, List<List<Integer>> list, List<Integer> ls) {
1. Create an empty queue
2. add node (root) to queue
3. start a loop until queue is not empty
4. find size of queue
5. again start a loop till size
dequeue node from queue and store its value into ls
check if node.left is not equal to null add node.left into queue
check if node.right is not equal to null add node.right into queue
6. add ls into list
}
Code Implementation:
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
public class LevelOrder {
static class Node {
int data;
Node left, right;
Node(int key) {
data = key;
left = right = null;
}
}
public static void main(String[] ans) {
Node root = new Node(2);
root.left = new Node(5);
root.right = new Node(10);
root.right.left = new Node(20);
root.right.right = new Node(30);
/* Level(s) nodes are stored in list */
List<List<Integer>> list = new ArrayList<>();
List<Integer> ls = new ArrayList<>();
levelOrder(root, list, ls);
System.out.println(list);
}
public static void levelOrder(Node root, List<List<Integer>> list, List<Integer> ls) {
if (root == null)
return;
/* Creating Queue */
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
ls = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node temp = queue.poll();
/*
* poll: deletes and returns the first element of the queue. This method returns
* null if queue is empty.
*/
ls.add(temp.data);
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
list.add(new ArrayList<>(ls));
}
}
}
Output:
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in tree.
Space Complexity: O(n), where n is the number of nodes in tree.
