Code Destine

Problem Statement

You have given a binary tree, return the level order traversal of its node values. In level order traversal, we traverse a binary tree from left to right and level by level.

Example 

Level order traversal of above binary tree is [3, 9, 20, 2, 6, 15, 7, 5, 8, 1]   

Algorithm 

In level order traversal, nodes of binary tree are traversed level by level and each level is traversed from left to right. Level order traversal can be implemented by using standard tree algorithms like depth first search and breadth first search.

Breadth First Search

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

public class LevelOrderTraversal {

	public static void main(String[] args) {
		
		LevelOrderTraversal pot = new LevelOrderTraversal();
		
		TreeNode node = new TreeNode(3);
		node.left = new TreeNode(9);
		node.right = new TreeNode(20);		
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(6);	
		
		TreeNode node1 = new TreeNode(15);
		TreeNode node2 = new TreeNode(7);
		
		node.right.left = node1;
		node.right.right = node2;	
		
		node1.left = new TreeNode(5);
		node1.right = new TreeNode(8);
		
		node2.right = new TreeNode(1);
		
		List<Integer> result = pot.levelOrderBottom(node);
		for(Integer i : result) {
			System.out.print(i+", ");
		}
	}
	
	public List<Integer> levelOrderBottom(TreeNode root) {
        
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int size = 0, i = 0;
        while(queue.size() > 0){
            
            size = queue.size();
            
            for(i = 0; i<size; i++){
                root = queue.poll(); 
                result.add(root.val);
                if(root.left != null) queue.add(root.left);                
                if(root.right != null) queue.add(root.right);
            }
        }
        return result;       
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}	
}

Depth First Search

import java.util.ArrayList;
import java.util.List;

public class LevelOrderTraversal {

	public static void main(String[] args) {
		
		LevelOrderTraversal pot = new LevelOrderTraversal();
		
		TreeNode node = new TreeNode(3);
		node.left = new TreeNode(9);
		node.right = new TreeNode(20);		
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(6);	
		
		TreeNode node1 = new TreeNode(15);
		TreeNode node2 = new TreeNode(7);
		
		node.right.left = node1;
		node.right.right = node2;	
		
		node1.left = new TreeNode(5);
		node1.right = new TreeNode(8);
		
		node2.right = new TreeNode(1);
		
		List<List<Integer>> result = pot.levelOrderBottom(node);
		for(List<Integer> list : result) {
			for(Integer i : list) {
				System.out.print(i+", ");
			}
		}
	}
	
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        dfs(root, 0, result);
        return result;
    }
    
    public void dfs(TreeNode node, int level, List<List<Integer>> result){
        
        if(node == null) return;
        
        if(result.size() < (level+1)){
            result.add(new ArrayList<>());
        }
        result.get(level).add(node.val);
        
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);        
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}	
}

Result

3, 9, 20, 2, 6, 15, 7, 5, 8, 1,

Similar Post

1. Minimum Distance Between BST Nodes
2. PreOrder Traversal of Tree
3. Average of Levels in Binary Tree

That’s all for Level Order Traversal of binary tree in Java, If you liked it, please share your thoughts in a comments section and share it with others too.