Level order traversal of a binary tree
Given a binary tree, print its nodes level by level, i.e., print all nodes of level 1 first, followed by nodes of level 2 and so on… Print nodes for any level from left to right.
For example, the level order traversal for the following tree is 1, 2, 3, 4, 5, 6, 7:
We have already discussed preorder, inorder and postorder traversals of the binary tree, which are nothing but variations of Depth–first search of a Tree. Trees can also be traversed in level order, where we visit every node on a level before going to a lower level. This search is referred to as level order traversal or Breadth–first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.
A simple solution is to print all nodes of level 1 first, followed by level 2, until level h, where h is the tree’s height. We can print all nodes present in a level by modifying the preorder traversal on the tree. This is demonstrated below in C++, Java, and Python:
C++
|
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 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Function to print all nodes of a given level from left to right bool printLevel(Node* root, int level) { if (root == nullptr) { return false; } if (level == 1) { cout << root->key << " "; // return true if at least one node is present at a given level return true; } bool left = printLevel(root->left, level - 1); bool right = printLevel(root->right, level - 1); return left || right; } // Function to print level order traversal of a given binary tree void levelOrderTraversal(Node* root) { // start from level 1 — till the height of the tree int level = 1; // run till printLevel() returns false while (printLevel(root, level)) { level++; } } int main() { Node* root = new Node(15); root->left = new Node(10); root->right = new Node(20); root->left->left = new Node(8); root->left->right = new Node(12); root->right->left = new Node(16); root->right->right = new Node(25); levelOrderTraversal(root); return 0; } |
Output:
15 10 20 8 12 16 25
Java
|
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 |
// A class to store a binary tree node class Node { int key; Node left = null, right = null; Node(int key) { this.key = key; } } class Main { // Function to print all nodes of a given level from left to right public static boolean printLevel(Node root, int level) { // base case if (root == null) { return false; } if (level == 1) { System.out.print(root.key + " "); // return true if at least one node is present at a given level return true; } boolean left = printLevel(root.left, level - 1); boolean right = printLevel(root.right, level - 1); return left || right; } // Function to print level order traversal of a given binary tree public static void levelOrderTraversal(Node root) { // start from level 1 — till the height of the tree int level = 1; // run till printLevel() returns false while (printLevel(root, level)) { level++; } } public static void main(String[] args) { Node root = new Node(15); root.left = new Node(10); root.right = new Node(20); root.left.left = new Node(8); root.left.right = new Node(12); root.right.left = new Node(16); root.right.right = new Node(25); levelOrderTraversal(root); } } |
Output:
15 10 20 8 12 16 25
Python
|
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 |
# A class to store a binary tree node class Node: def __init__(self, key=None, left=None, right=None): self.key = key self.left = left self.right = right # Function to print all nodes of a given level from left to right def printLevel(root, level): # base case if root is None: return False if level == 1: print(root.key, end=' ') # return true if at least one node is present at a given level return True left = printLevel(root.left, level - 1) right = printLevel(root.right, level - 1) return left or right # Function to print level order traversal of a given binary tree def levelOrderTraversal(root): # start from level 1 — till the height of the tree level = 1 # run till printLevel() returns false while printLevel(root, level): level = level + 1 if __name__ == '__main__': root = Node(15) root.left = Node(10) root.right = Node(20) root.left.left = Node(8) root.left.right = Node(12) root.right.left = Node(16) root.right.right = Node(25) levelOrderTraversal(root) |
Output:
15 10 20 8 12 16 25
The time complexity of the above solution is O(n2), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.
We can reduce the time complexity to O(n) by using extra space. Following is a pseudocode for a simple queue-based level order traversal, which requires space proportional to the maximum number of nodes at a given depth. It can be as much as half the total number of nodes.
q —> empty queue
q.enqueue(root)
while (not q.isEmpty())
node —> q.dequeue()
visit(node)
if (node.left <> null)
q.enqueue(node.left)
if (node.right <> null)
q.enqueue(node.right)
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
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 |
#include <iostream> #include <list> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Function to print level order traversal of a given binary tree void levelOrderTraversal(Node* root) { // base case if (root == nullptr) { return; } // create an empty queue and enqueue the root node list<Node*> queue; queue.push_back(root); // pointer to store the current node Node* curr = nullptr; // loop till queue is empty while (queue.size()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.front(); queue.pop_front(); cout << curr->key << " "; if (curr->left) { queue.push_back(curr->left); } if (curr->right) { queue.push_back(curr->right); } } } int main() { Node* root = new Node(15); root->left = new Node(10); root->right = new Node(20); root->left->left = new Node(8); root->left->right = new Node(12); root->right->left = new Node(16); root->right->right = new Node(25); levelOrderTraversal(root); return 0; } |
Output:
15 10 20 8 12 16 25
Java
|
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 |
import java.util.ArrayDeque; import java.util.Queue; // A class to store a binary tree node class Node { int key; Node left = null, right = null; Node(int key) { this.key = key; } } class Main { // Function to print level order traversal of a given binary tree public static void levelOrderTraversal(Node root) { // base case if (root == null) { return; } // create an empty queue and enqueue the root node Queue<Node> queue = new ArrayDeque<>(); queue.add(root); // to store the current node Node curr; // loop till queue is empty while (!queue.isEmpty()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.poll(); System.out.print(curr.key + " "); if (curr.left != null) { queue.add(curr.left); } if (curr.right != null) { queue.add(curr.right); } } } public static void main(String[] args) { Node root = new Node(15); root.left = new Node(10); root.right = new Node(20); root.left.left = new Node(8); root.left.right = new Node(12); root.right.left = new Node(16); root.right.right = new Node(25); levelOrderTraversal(root); } } |
Output:
15 10 20 8 12 16 25
Python
|
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 |
from collections import deque # A class to store a binary tree node class Node: def __init__(self, key=None, left=None, right=None): self.key = key self.left = left self.right = right # Function to print level order traversal of a given binary tree def levelOrderTraversal(root): # base case if not root: return # create an empty queue and enqueue the root node queue = deque() queue.append(root) # loop till queue is empty while queue: # process each node in the queue and enqueue their # non-empty left and right child curr = queue.popleft() print(curr.key, end=' ') if curr.left: queue.append(curr.left) if curr.right: queue.append(curr.right) if __name__ == '__main__': root = Node(15) root.left = Node(10) root.right = Node(20) root.left.left = Node(8) root.left.right = Node(12) root.right.left = Node(16) root.right.right = Node(25) levelOrderTraversal(root) |
Output:
15 10 20 8 12 16 25
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the binary tree.
We can also solve this problem by using hashing. The idea is to traverse the tree in a preorder fashion and store every node and its level in a multimap using the level number as a key. Finally, print all nodes corresponding to every level starting from the first level. We can also traverse the tree in inorder or postorder fashion.
Following is the implementation of the above approach in C++, Java, and Python:
C++
|
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 |
#include <iostream> #include <vector> #include <unordered_map> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Traverse the tree in a preorder fashion and store nodes in a map // corresponding to their level void preorder(Node* root, int level, auto &map) { // base case: empty tree if (root == nullptr) { return; } // insert the current node and its level into the map map[level].push_back(root->key); // recur for the left and right subtree by increasing the level by 1 preorder(root->left, level + 1, map); preorder(root->right, level + 1, map); } // Recursive function to print level order traversal of a given binary tree void levelOrderTraversal(Node* root) { // create an empty map to store nodes between given levels unordered_map<int, vector<int>> map; // traverse the tree and insert its nodes into the map // corresponding to their level preorder(root, 1, map); // iterate through the map and print all nodes between given levels for (int i = 1; map[i].size() > 0; i++) { cout << "Level " << i << ": "; for (int j: map[i]) { cout << j << " "; } cout << endl; } } int main() { Node* root = new Node(15); root->left = new Node(10); root->right = new Node(20); root->left->left = new Node(8); root->left->right = new Node(12); root->right->left = new Node(16); root->right->right = new Node(25); root->right->right->right = new Node(30); levelOrderTraversal(root); return 0; } |
Output:
Level 1: 15
Level 2: 10 20
Level 3: 8 12 16 25
Level 4: 30
Java
|
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 |
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; // A class to store a binary tree node class Node { int key; Node left = null, right = null; Node(int key) { this.key = key; } } class Main { // Traverse the tree in a preorder fashion and store nodes in a map // corresponding to their level public static void preorder(Node root, int level, Map<Integer, List<Integer>> map) { // base case: empty tree if (root == null) { return; } // insert the current node and its level into the map map.putIfAbsent(level, new ArrayList<>()); map.get(level).add(root.key); // recur for the left and right subtree by increasing the level by 1 preorder(root.left, level + 1, map); preorder(root.right, level + 1, map); } // Recursive function to print level order traversal of a given binary tree public static void levelOrderTraversal(Node root) { // create an empty map to store nodes between given levels Map<Integer, List<Integer>> map = new HashMap<>(); // traverse the tree and insert its nodes into the map // corresponding to their level preorder(root, 1, map); // iterate through the map and print all nodes between given levels for (int i = 1; i <= map.size(); i++) { System.out.println("Level " + i + ": " + map.get(i)); } } public static void main(String[] args) { Node root = new Node(15); root.left = new Node(10); root.right = new Node(20); root.left.left = new Node(8); root.left.right = new Node(12); root.right.left = new Node(16); root.right.right = new Node(25); root.right.right.right = new Node(30); levelOrderTraversal(root); } } |
Output:
Level 1: 15
Level 2: 10 20
Level 3: 8 12 16 25
Level 4: 30
Python
|
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 |
# A class to store a binary tree node class Node: def __init__(self, key=None, left=None, right=None): self.key = key self.left = left self.right = right # Traverse the tree in a preorder fashion and store nodes in a dictionary # corresponding to their level def preorder(root, level, d): # base case: empty tree if root is None: return # insert the current node and its level into the dictionary d.setdefault(level, []).append(root.key) # recur for the left and right subtree by increasing the level by 1 preorder(root.left, level + 1, d) preorder(root.right, level + 1, d) # Recursive function to print level order traversal of a given binary tree def levelOrderTraversal(root): # create an empty dictionary to store nodes between given levels d = {} # traverse the tree and insert its nodes into the dictionary # corresponding to their level preorder(root, 1, d) # iterate through the dictionary and print all nodes between given levels for i in range(1, len(d) + 1): print(f'Level {i}:', d[i]) if __name__ == '__main__': root = Node(15) root.left = Node(10) root.right = Node(20) root.left.left = Node(8) root.left.right = Node(12) root.right.left = Node(16) root.right.right = Node(25) root.right.right.right = Node(30) levelOrderTraversal(root) |
Output:
Level 1: [15]
Level 2: [10, 20]
Level 3: [8, 12, 16, 25]
Level 4: [30]
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the binary tree.
Exercise: Modify the solution to print nodes of different levels in a separate line.
References: https://en.wikipedia.org/wiki/Tree_traversal
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)