package DataStructures.Trees;

public class LevelOrderTraversal {

  class Node {
    int data;
    Node left, right;

    public Node(int item) {
      data = item;
      left = right = null;
    }
  }

  // Root of the Binary Tree
  Node root;

  public LevelOrderTraversal(Node root) {
    this.root = root;
  }

  /* function to print level order traversal of tree*/
  void printLevelOrder() {
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++) printGivenLevel(root, i);
  }

  /* Compute the "height" of a tree -- the number of
  nodes along the longest path from the root node
  down to the farthest leaf node.*/
  int height(Node root) {
    if (root == null) return 0;
    else {
      /** Return the height of larger subtree */
      return Math.max(height(root.left), height(root.right)) + 1;
    }
  }

  /* Print nodes at the given level */
  void printGivenLevel(Node root, int level) {
    if (root == null) return;
    if (level == 1) System.out.print(root.data + " ");
    else if (level > 1) {
      printGivenLevel(root.left, level - 1);
      printGivenLevel(root.right, level - 1);
    }
  }
}