Given a binary tree, print the level order traversal of its node’s values.
For example:
Given below binary tree, the level order traversal of this binary tree is 7, 6, 5, 4, 3, 2, 1.
level by level traversal of binary tree
In this tutorial, I am going to discuss level order traversal and its implementation using java code.
At the end of this tutorial, You’ll find a video link in which i have explained level by level traversal of binary tree using queue.
Level Order Traversal
Algorithm to Print Level Order Traversal using Queue
i) Declare a queue and add root node in a queue.
ii) Run a while loop while queue is not empty and do the following steps
a) poll a queue and print the node data.
b) Enqueue left and right children of a node if it’s not null.
Implement queue using two stacks
Find next greater element in an array
Binary Tree Level Order Traversal – Java Code
We have discussed the algorithm, let’s implement level by level traversal of binary tree using queue.
The time complexity of level order traversal is O(n) and it’s space complexity is also O(n).
Reverse level order traversal of a binary tree
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
/* Level Order or Breadth First Traversal */ public class LevelOrderTraversal { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; } } public static void levelOrderTraversal(TreeNode node) { /* Declare a queue and add root node of a tree */ Queue queue = new LinkedList<>(); queue.add(node); //While queue is not empty while (!queue.isEmpty()) { //Retrieve and remove the head of the queue TreeNode nodeData = queue.poll(); //print the data part System.out.print(nodeData.data + " "); /* If left children is not null, then enqueue in a queue */ if (nodeData.left != null) { queue.add(nodeData.left); } /* If right children is not null, then enqueue in a queue */ if (nodeData.right != null) { queue.add(nodeData.right); } } } public static TreeNode createBinaryTree() { TreeNode rootNode = new TreeNode(7); rootNode.left = new TreeNode(6); rootNode.right = new TreeNode(5); rootNode.left.left = new TreeNode(4); rootNode.left.right = new TreeNode(3); rootNode.right.left = new TreeNode(2); rootNode.right.right = new TreeNode(1); return rootNode; } public static void main(String[] args) { levelOrderTraversal(createBinaryTree()); } } |
In this example, we have printed the output in a single line.
Let’s write another version of this code in which we print the binary tree level by level.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
//Visit node level by level public static List<list> levelOrder(TreeNode node) { /* Declare a list, which holds list of values. */ List<list> result = new ArrayList<>(); //If node is null, return empty list if (node == null) { return result; } //Declare a queue Queue qu = new LinkedList<>(); //Add root node qu.add(node); //Run a loop, until queue is not empty while (!qu.isEmpty()) { int size = qu.size(); List currentLevel = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode temp = qu.poll(); currentLevel.add(temp.data); if (temp.left != null) { qu.add(temp.left); } if (temp.right != null) { qu.add(temp.right); } } result.add(currentLevel); } return result; } </list</list |
Video Tutorial
