BinarayTreeLevelOrderTraversal.java

package breadth_first_search;

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

/**
 * Created by gouthamvidyapradhan on 13/03/2017. Given a binary tree, return the level order
 * traversal of its nodes' values. (ie, from left to right, level by level).
 *
 * <p>For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level
 * order traversal as: [ [3], [9,20], [15,7] ]
 */
public class BinarayTreeLevelOrderTraversal {
  public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private class LevelNode {
    TreeNode node;
    int level;

    LevelNode(TreeNode node, int level) {
      this.node = node;
      this.level = level;
    }
  }

  /**
   * Main method
   *
   * @param args
   * @throws Exception
   */
  public static void main(String[] args) throws Exception {
    TreeNode root = new TreeNode(2);
    root.left = new TreeNode(3);
    root.right = new TreeNode(4);
    root.right.right = new TreeNode(5);
    root.right.left = new TreeNode(4);
    root.right.left.right = new TreeNode(8);
    root.right.left.left = new TreeNode(7);
    root.right.left.left.right = new TreeNode(10);
    root.right.left.left.left = new TreeNode(9);

    List<List<Integer>> result = new BinarayTreeLevelOrderTraversal().levelOrder(root);
  }

  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<LevelNode> queue = new ArrayDeque<>();
    queue.offer(new LevelNode(root, 0));
    int currentLevel = 0;
    List<Integer> row = new ArrayList<>();
    while (!queue.isEmpty()) {
      LevelNode levelNode = queue.poll();
      if (levelNode.node != null) {
        if (levelNode.level != currentLevel) {
          result.add(row);
          row = new ArrayList<>();
          currentLevel++;
        }
        row.add(levelNode.node.val);
        TreeNode left = levelNode.node.left;
        TreeNode right = levelNode.node.right;
        LevelNode lNodeL = new LevelNode(left, levelNode.level + 1);
        LevelNode lNodeR = new LevelNode(right, levelNode.level + 1);
        queue.offer(lNodeL);
        queue.offer(lNodeR);
      }
    }
    result.add(row);
    return result;
  }
}