Binary Tree Level Order Traversal

Problem:

Write a program to in order traversal a binary tree from left to right and level by level.

For example:

Given binary tree 

    1

   / \

  2   3

 / \   \

4   5   6

it's in order traversal sequence is:

1 

2 3 

4 5 6

follow up question:

I see, you did this iteratively (recursively). Can you also solve it with recursive (iterative) approach?

Solution:

Iterative approach is easier. We are actually BFS traversal the binary tree start from root. We use a queue to store the nodes, after process the node at the top of the queue, we add its children nodes. The number of nodes at each level can be calculated by the queue size before we start processing the nodes at that level.

The recursive approach need a helper List<List<Integer>>. We add a new List<Integer> for each new level. At a particular level, we add the current processing node to the corresponding List<List<Integer>. Then we recursively process the left node and the right node.

import java.util.*;
class Solution {
  public static void main(String...args) {
    Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6)));
    levelOrderIterative(root);
    System.out.println();
    levelOrderRecursive(root);
  }
 
  private static void levelOrderIterative(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int size = queue.size();
    while(!queue.isEmpty()) {
      size = queue.size();
      for(int i = 1; i <= size; i++) {
        root = queue.poll();
        System.out.print(root.val + " ");
        if(root.left != null)
          queue.offer(root.left);
        if(root.right != null)
          queue.offer(root.right);
      }
      System.out.println();
    }
  }
 
  private static void levelOrderRecursive(Node root) {
    List<List<Integer>> result = new ArrayList<>();
    levelOrder(root, 0, result);
    for(List<Integer> lNodes : result) {
      for(Integer i : lNodes) {
        System.out.print(i + " ");
      }
      System.out.println();
    }
  }
 
  private static void levelOrder(Node root, int level, List<List<Integer>> result) {
    if(root == null)
      return;
    if(level == result.size())
      result.add(new ArrayList<>());
    result.get(level).add(root.val);
    levelOrder(root.left, level + 1, result);
    levelOrder(root.right, level + 1, result);
  }
  private static class Node {
    Node left;
    Node right;
    int val;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
    public Node(int val) {
      this.val = val;
      this.left = null;
      this.right = null;
    }
  }
}

The time complexity is O(N), the space complexity is O(N) as well.