Traversing a tree using LevelOrder traveral

package in.blogspot.arunj2ee.ds.tree.traversal;

import in.blogspot.arunj2ee.ds.tree.BinaryTreeNode;
import in.blogspot.arunj2ee.ds.tree.util.TreeUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/*
   Nice Implemnetation
 * Traversing a tree using LevelOrder traveral
 * Time Complexity: O(n), Space Complexity: O(n)
 * @author Arun.Singh
 */
public class LevelOrderTraversal {
public static ArrayList<ArrayList<Integer>> levelOrderTraversal(BinaryTreeNode root){
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(root == null)
return res;

// Initialization
Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
q.offer(root);
q.offer(null);

ArrayList<Integer> curr = new ArrayList<Integer>();
while(!q.isEmpty()){
BinaryTreeNode tmp = q.poll();
if(tmp != null){
curr.add(tmp.getData());
if(tmp.getLeft() != null)
q.offer(tmp.getLeft());
if(tmp.getRight() != null)
q.offer(tmp.getRight());
}else{
ArrayList<Integer> c_curr = new ArrayList<Integer>(curr);
res.add(c_curr);
curr.clear(); // Java will clear the reference, so have to new as new ArrayList
// Completion of a level
if(!q.isEmpty())
q.offer(null);
}
}
return res;
}

// [[1], [2, 3], [4, 5, 6, 7]]
public static void main(String[] args) {
System.out.println(levelOrderTraversal(TreeUtil.makeSampleBinaryTree()));
}
}

========================================================================

Refer Core Classes: http://arunj2ee.blogspot.in/2017/05/tree-core-and-utility-classes.html

========================================================================

Share on Google Plus

About Admin

Arun is a JAVA/J2EE developer and passionate about coding and managing technical team.