Tree Traversals - Breadth First or level order (Iterative/ Non Recursive Approach)
In our previous article we have learned that being a hierarchical data structure binary tree can be traversed in more than one way. We have already covered the depth first traversal of the tree in the article here - Tree Traversals - Depth First. In this article we will cover the Breadth First or Level Order traversal of a binary tree.
Breadth First or level Order Traversal - In this approach we visit all the nodes of a tree at a particular level before moving to another level. We start the traversal starting from the root node and move downward in the tree visiting all the nodes of the level until we finish the last level of the tree.
For example lets assume we have a binary tree with structure as shown in the figure below -
Now if we print the nodes of this tree using the level order traversal we will get the keys in this sequence - 5 3 8 2 4 6 10
Level order traversal implementation -
package ds.tree;
import java.util.LinkedList;
import java.util.Queue;
public class BStree {
private Node root;
public BStree(int rootData) {
this.root = new Node(rootData);
// TODO Auto-generated constructor stub
}
static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
public void insert(int data) {
Node nNode = new Node(data);
Node root = this.root;
Node nodeB = null;
while (root != null) {
nodeB = root;
if (root.data > data) {
root = root.left;
} else {
root = root.right;
}
}
if(data < nodeB.data)
nodeB.left = nNode;
else
nodeB.right = nNode;
}
public void levelOrder() {
Queue<Node> queue = new LinkedList<BStree.Node>();
queue.add(this.root);
while(!queue.isEmpty()) {
Node cNode = queue.poll();
System.out.print(cNode.data + " ");
if(cNode.left != null)
queue.add(cNode.left);
if(cNode.right != null)
queue.add(cNode.right);
}
}
}
In the binary tree implementation above public method levelOrder() has been implemented to traverse the tree in level order fashion and print its keys. We have used a FIFO queue for the implementation which is responsible to arrange the nodes at the next level in right order, then we are printing each node one by one using a while loop untill queue is empty.
Now lets write a simple main method to create a binary search tree with some elements in it and try printing it using level order traveral.
Now lets write a simple main method to create a binary search tree with some elements in it and try printing it using level order traveral.
package ds.tree;
public class BtreeMain {
public static void main(String[] args) {
BStree bst = new BStree(5);
bst.insert(3);
bst.insert(8);
bst.insert(6);
bst.insert(4);
bst.insert(2);
bst.insert(10);
bst.levelOrder();
}
}
Output: 5 3 8 2 4 6 10
Comments
Post a Comment