Level order tree traversal
In Level-Order tree traversal, the data in the nodes is accessed level-wise from the top i.e from root level all the way down to the bottom of the tree.
Algorithm : Level-Order traversal
1. Create two queues / lists; one for storing the parent and the other for storing the children.
2. Push the root node into the parent queue.
3. While the parent queue or the child queue is not empty, do
4. While the parent queue is not empty do
5. Pop-out node P from the parent queue and print it.
6. If node P has children, then add it to the queue for children.
7. While the child queue is not empty, do
8. Pop-out node C from the child queue and print it.
9. If node C has children, then add it to the queue for the parent.
Example of level-order tree traversal Consider the level-order tree traversal for the above tree Step 1: Node 9 being the root, it gets pushed into the Parent Queue i.e PQ [ 9 ]. Step 2: Since the Parent Queue PQ [ 9 ] is not empty, pop out the node 9 and print it. Step 3: As the node 9 has children 5 and 16, add them to the Child Queue CQ [ 5, 16 ]. Step 4: Since the Child Queue CQ [ 5, 16 ] is not empty, pop out node 5 and print it. As the node 5 has children 3 and 7, add them to the Parent Queue PQ [ 3, 7 ]. Pop out the second node 16 from the Child Queue and print it. As the node 16 has children 12 and 18, add them to the Parent Queue PQ [ 3, 7, 12, 18 ]. …
From the above it is easy to see that node 9 gets accessed first in Step 2, its children 5 and 16 get accessed in Step 4 and so on.
Level order traversals Level 0 : 9 Level 1 : 5 16 Level 2 : 3 7 12 18 Level 3 : 6 8 25 Level 4 : 20 36
Data structure : Queue
Time Complexity : O ( n ), where n is the number of nodes in the tree. As the push O ( 1 ) and pop O ( 1 ) operations happen only once for every node in the tree the time complexity is O ( n ).
Level order tree traversal implementation
import queue
class Node :
def __init__(self, data=0, left=None, right=None) :
self.data = data
self.left = left
self.right = right
def LevelOrder (root) :
if root == None :
return
parent_queue = queue.Queue()
child_queue = queue.Queue()
parent_queue.put (root)
# Level 0 corresponds to the top of the tree i.e at the root level
level = 0
while parent_queue.empty() == False or child_queue.empty() == False :
if parent_queue.empty() == False :
print ("\nLevel " + str(level) + " : ", end=" ")
while parent_queue.empty() == False :
node = parent_queue.get()
print (node.data, end=" ")
if node.left != None :
child_queue.put (node.left)
if node.right != None :
child_queue.put (node.right)
level += 1
if child_queue.empty() == False :
print ( "\nLevel " + str(level) + " : ", end=" ")
while child_queue.empty() == False:
node = child_queue.get()
print (node.data, end=" ")
if node.left != None :
parent_queue.put (node.left)
if node.right != None :
parent_queue.put (node.right)
level += 1
def main() :
# Constructed binary tree is
# 9
# / \
# 5 16
# / \ / \
# 3 7 12 18
# / \ \
# 6 8 25
# / \
# 20 36
#
node_6 = Node(6, None, None)
node_8 = Node(8, None, None)
node_12 = Node(12, None, None)
node_20 = Node(20, None, None)
node_36 = Node(36, None, None)
node_25 = Node(25, node_20, node_36)
node_3 = Node(3, None, None)
node_7 = Node(7, node_6, node_8)
node_5 = Node(5, node_3, node_7)
node_18 = Node(18, None, node_25)
node_16 = Node(16, node_12, node_18)
root = Node(9, node_5, node_16)
LevelOrder(root)
if __name__ == "__main__":
main()
Output
Level 0 : 9
Level 1 : 5 16
Level 2 : 3 7 12 18
Level 3 : 6 8 25
Level 4 : 20 36
#include<iostream>
#include<queue>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node() : data(0), left(nullptr), right(nullptr) {}
Node(int x) : data(x), left(nullptr), right(nullptr) {}
Node(int x, Node *left, Node *right) : data(x), left(left), right(right) {}
};
void LevelOrder (Node * root) {
if(root == NULL)
return;
queue<Node *> parent_queue, child_queue;
parent_queue.push(root);
// Level 0 corresponds to the top of the tree i.e at the root level
int level = 0;
while (!parent_queue.empty() or !child_queue.empty()) {
if (!parent_queue.empty())
cout << "Level " << level << ": ";
while (!parent_queue.empty()) {
Node * node = parent_queue.front();
parent_queue.pop();
cout << node->data << " ";
if (node->left != NULL)
child_queue.push(node->left);
if (node->right != NULL)
child_queue.push(node->right);
}
cout << endl;
level++;
if (!child_queue.empty())
cout << "Level " << level << ": ";
while (!child_queue.empty()) {
Node * node = child_queue.front();
child_queue.pop();
cout << node->data << " ";
if (node->left != NULL)
parent_queue.push(node->left);
if (node->right != NULL)
parent_queue.push(node->right);
}
cout << endl;
level++;
}
}
int main() {
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
/ \ \
6 8 25
/ \
20 36
*/
Node node_6 (6, nullptr, nullptr);
Node node_8 (8, nullptr, nullptr);
Node node_12 (12, nullptr, nullptr);
Node node_20 (20, nullptr, nullptr);
Node node_36 (36, nullptr, nullptr);
Node node_25 (25, &node_20, &node_36);
Node node_3 (3, nullptr, nullptr);
Node node_7 (7, &node_6, &node_8);
Node node_5 (5, &node_3, &node_7);
Node node_18 (18, nullptr, &node_25);
Node node_16 (16, &node_12, &node_18);
Node root (9, &node_5, &node_16);
LevelOrder(&root);
return 0;
}
Output
Level 0: 9
Level 1: 5 16
Level 2: 3 7 12 18
Level 3: 6 8 25
Level 4: 20 36
import java.util.Queue;
import java.util.LinkedList;
class TreeTraversal {
static class Node {
int data;
Node left;
Node right;
Node () {}
Node (int data) { this.data = data; }
Node (int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}
void LevelOrder (Node root) {
if (root == null)
return;
Queue<Node> parent_queue = new LinkedList<>();
Queue<Node> child_queue = new LinkedList<>();
parent_queue.add(root);
// Level 0 corresponds to the top of the tree i.e at the root level
int level = 0;
while (!parent_queue.isEmpty() || !child_queue.isEmpty()) {
if (!parent_queue.isEmpty())
System.out.print("Level " + level + ": ");
while (!parent_queue.isEmpty()) {
Node node = parent_queue.remove();
System.out.print(node.data + " ");
if (node.left != null)
child_queue.add(node.left);
if (node.right != null)
child_queue.add(node.right);
}
System.out.println();
level++;
if (!child_queue.isEmpty())
System.out.print("Level " + level + ": ");
while (!child_queue.isEmpty()) {
Node node = child_queue.remove();
System.out.print(node.data + " ");
if (node.left != null)
parent_queue.add(node.left);
if (node.right != null)
parent_queue.add(node.right);
}
System.out.println();
level++;
}
}
public static void main (String[] args) {
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
/ \ \
6 8 25
/ \
20 36
*/
Node node_6 = new Node(6, null, null);
Node node_8 = new Node(8, null, null);
Node node_12 = new Node(12, null, null);
Node node_20 = new Node(20, null, null);
Node node_36 = new Node(36, null, null);
Node node_25 = new Node(25, node_20, node_36);
Node node_3 = new Node(3, null, null);
Node node_7 = new Node(7, node_6, node_8);
Node node_5 = new Node(5, node_3, node_7);
Node node_18 = new Node(18, null, node_25);
Node node_16 = new Node(16, node_12, node_18);
Node root = new Node(9, node_5, node_16);
TreeTraversal t = new TreeTraversal();
t.LevelOrder (root);
}
}
Output
Level 0: 9
Level 1: 5 16
Level 2: 3 7 12 18
Level 3: 6 8 25
Level 4: 20 36