Level Order Traversal
This algorithm is equivalent to breadth-first search traversal in which the nodes at every depth are processed before proceeding to the next level. In this algorithm, all nodes at the same depth are traversed and repeated until the maximum depth of the tree.
Binary Tree
A binary tree is a non-linear data structure in which every node has at a most maximum of two children. So, in terms of binary tree construction, we should have a node with three-pointers one to hold data and two for left and right nodes.
class Tree {
public class Node {
int data;
Node right;
Node left;
Node(int data) {
this.data = data;
left = right = null;
}
}
In this above tree class with inner node class has one instance member data and two objects of Node class left and right. For every new node, we use Node(int data ) constructor to assign data to that node and set left and right as null.
Tree.Node t = new Tree().new Node(1);
t.left = new Tree().new Node(2);
t.left.left = new Tree().new Node(4);
t.left.right = new Tree().new Node(5);
t.right = new Tree().new Node(3);
Algorithm :
- Create a queue for holding node elements
- push the root to queue
- Iterate through the left and right subtree till queue is not empty
- for every node print the node and push the left and right subtree to the queue
Program for level order traversal:
public void levelOrder(Node root) {
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node e = q.poll();
System.out.print(e.data + " ");
if (e.left != null) {
q.offer(e.left);
}
if (e.right != null) {
q.offer(e.right);
}
}
}
Consider the above tree diagram with root vertex at 1 is being pushed to queue and in
while loop the first element of the queue that is 1 is being processed and left element 2 is
being pushed to queue and then the right element 3 to the tree.
I hope you guys liked this article, here are some other articles you may like:
0 Comments