## Problem Statement
Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree.

Level order traversal for this tree should look like:
* 100
* 50, 200
* 25, 75, 350

<br>

## Hint
* Breadth first traversal

<br>

## Try it yourself

string level_order_traversal(BinaryTreeNode* root) {
  string result = "";
  //TODO: Write - Your - Code
  
  return result;
}

#include <iostream>
#include <vector>
#include <queue>
#include <assert.h>
#include <time.h>
#include <math.h>
#include <stack>
#include <cstdlib>
using namespace std;


struct BinaryTreeNode
{
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode* parent;

    // below data members used only for some of the problems
    BinaryTreeNode* next;
    int count;

    BinaryTreeNode(int d) : data(d), left(nullptr), right(nullptr), next(nullptr), parent(nullptr), count(0) {
    }
};

BinaryTreeNode* insert_bst(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (d < parent->data) {
    parent->left = pNew;
  } else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* find_in_bst(BinaryTreeNode* root, int d) {
  if(root == nullptr)
    return nullptr;

  if(root->data == d) {
    return root;
  }
  else if( root->data > d)
  {
    return find_in_bst(root->left, d);
  }
  else
  {
    return find_in_bst(root->right,d);
  }
}

BinaryTreeNode* insert_binary_tree(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (rand()%2 == 0) {
    parent->left = pNew;
  }
  else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* create_BinaryTree(int count) {
  BinaryTreeNode* root = nullptr;
  for (int i = 0; i < count; ++i) {
    int r = rand() % 100;
    root = insert_binary_tree(root, r);
  }
  return root;
}

void display_inorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  display_inorder(node->left);
  cout << node->data << ", ";
  display_inorder(node->right);
}

void get_inorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  get_inorder(node->left, output);
  output.push_back(node->data);
  get_inorder(node->right, output);
}

void display_preorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  cout << node->data << ", ";

  display_preorder(node->left);
  display_preorder(node->right);
}

void get_preorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  output.push_back(node->data);
  get_inorder(node->left, output);
  get_inorder(node->right, output);
}

BinaryTreeNode* create_BST(vector<int>& v) {
  BinaryTreeNode* root = nullptr;
  int count = 0;
  for (int x : v) {
    root = insert_bst(root, x);
    if (count % 50000 == 0) {
      cout << "Inserted " << count << endl;
    }
    ++count;
  }
  return root;
}

BinaryTreeNode* create_random_BST(int count) {
  BinaryTreeNode* root = nullptr;
  srand(time(NULL));
  for (int i = 0; i < count; ++i) {
      int r =  rand() % 997;
      root = insert_bst(root, r);
  }
  return root;
}

void binary_tree_to_vector_rec(BinaryTreeNode* root, vector<int>& v) {
  if (root == nullptr) {
    return;
  }

  binary_tree_to_vector_rec(root->left, v);
  v.push_back(root->data);
  binary_tree_to_vector_rec(root->right, v);
}

vector<int> binary_tree_to_vector(BinaryTreeNode* root) {
  vector<int> v;
  binary_tree_to_vector_rec(root, v);
  return v;
}

string display_BT(BinaryTreeNode* root) {
  string result = "";
  if (root == nullptr) {
    return "";
  }

  queue<BinaryTreeNode*> q;
  q.push(root);
  q.push(nullptr);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();
    result += std::to_string(temp->data) +", ";
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }

    if (q.front() == nullptr) {
      q.pop();
      if (!q.empty()) {
        q.push(nullptr);
      }
    }

  }
  return result;
}

void get_level_order(BinaryTreeNode* root, vector<int>& output) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> q;
  q.push(root);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();

    output.push_back(temp->data);
    
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }
  }
}

void another_display_tree(BinaryTreeNode* root, int tabs) {
  if (root != nullptr) {
    int i;

    if (root->left != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "L" << root->left->data << endl;
    }

    if (root->right != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "R" << root->right->data << endl;
    }

    another_display_tree(root->left, tabs + 4);
    another_display_tree(root->right, tabs + 4);
  }
}

void another_display_tree(BinaryTreeNode* root) {
  if (root != nullptr) {
    cout << root->data << endl;
    another_display_tree(root, 0);
  }
}

bool is_identical_tree(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  else if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            is_identical_tree(root1->left, root2->left) &&
            is_identical_tree(root1->right, root2->right));
  }
  else {
    return false;
  }
}

void populate_parents_rec(BinaryTreeNode* root, BinaryTreeNode* parent) {
  if (root == nullptr) {
    return;
  }

  root->parent = parent;

  populate_parents_rec(root->left, root);
  populate_parents_rec(root->right, root);
}

void populate_parents(BinaryTreeNode* root) {
  populate_parents_rec(root, nullptr);
}

bool are_identical_trees(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  
  if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            are_identical_trees(root1->left, root2->left) &&
            are_identical_trees(root1->right, root2->right));
  }

  return false;
}

class levelOrderTraversal{
    
  public static String level_order_traversal(
      BinaryTreeNode root) {
      //TODO: Write - Your - Code
        return "";
  }
} 

import java.util.*;
import java.math.*;

class BinaryTreeNode
{
    public int data;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    // below data members used only for some of the problems
    public BinaryTreeNode next;
    public BinaryTreeNode parent;
    public int count;

    public BinaryTreeNode(int d) {
      data = d;
      left = null;
      right = null;
      parent = null;
      count = 0;
    }
}
class BinaryTree {

public static BinaryTreeNode root;

public BinaryTree() {
  root = null;
}

public BinaryTree(BinaryTreeNode head) {
  this.root = head;
}

public static BinaryTreeNode insert(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  if (d <= parent.data) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode insert_BT(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  Random generator = new Random();
  int dir = generator.nextInt(1000);

  if (dir%2 == 0) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode find_in_bst(BinaryTreeNode root, int d){
  if(root == null)
    return null;

  if(root.data == d) {
    return root;
  }
  else if(root.data > d){
    return find_in_bst(root.left,d);
  }
  else{
    return find_in_bst(root.right,d);
  }
}


public static void display_inorder(BinaryTreeNode node) {
  if (node == null) {
    return;
  }
  display_inorder(node.left);
  if(node.parent != null)
  {
    //System.out.print(String.format("[%d - %d]",node.parent.data, node.count));
  }
  System.out.print(node.data + ", ");
  display_inorder(node.right);
}

public static void get_inorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  get_inorder(node.left, output);
  output.add(node.data);
  get_inorder(node.right, output);
}

public static void get_preorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  output.add(node.data);
  get_preorder(node.left, output);
  get_preorder(node.right, output);
}

public static BinaryTreeNode create_BST(List<Integer> l) {
  BinaryTreeNode root = null;
  for (Integer x : l) {
    root = insert(root, x);
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count, int max_value) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert(root, generator.nextInt(max_value));
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count) {
  return create_random_BST(count, Integer.MAX_VALUE);
}

public static BinaryTreeNode create_binary_tree(int count) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert_BT(root, generator.nextInt(100));
  }
  return root;
}

private static void populate_parents_rec(BinaryTreeNode root, BinaryTreeNode parent) {
  if (root == null) {
    return;
  }

  root.parent = parent;

  populate_parents_rec(root.left, root);
  populate_parents_rec(root.right, root);
}

public static void populate_parents(BinaryTreeNode root) {
  populate_parents_rec(root, null);
}

public static void bst_to_arraylist_rec(BinaryTreeNode root, ArrayList<Integer> arr) {
  if (root == null) {
    return;
  }

  bst_to_arraylist_rec(root.left, arr);
  arr.add(root.data);
  bst_to_arraylist_rec(root.right, arr);
}

public static ArrayList<Integer> bst_to_arraylist(BinaryTreeNode root) {
  ArrayList<Integer> arr = new ArrayList<Integer>();
  bst_to_arraylist_rec(root, arr);
  return arr;
}

public static void another_display_tree(BinaryTreeNode root, int tabs) {
  if (root != null) {
    int i;

    if (root.left != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("L" + root.left.data + "\n");
    }

    if (root.right != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("R" + root.right.data + "\n");
    }

    another_display_tree(root.left, tabs + 4);
    another_display_tree(root.right, tabs + 4);
  }
}

public static void another_display_tree(BinaryTreeNode root) {
  if (root != null) {
    System.out.print(root.data + "\n");
    another_display_tree(root, 0);
  }
}

public static void display_level_order(BinaryTreeNode root) {
  if(root == null)
    return;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    System.out.print(temp.data + ", ");

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
    System.out.println();
}

public static List<Integer> get_level_order(BinaryTreeNode root) {

  List<Integer> output = new ArrayList<Integer>();

  if(root == null)
    return output;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    // System.out.print(temp.data + ", ");
    output.add(temp.data);

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
  return output;
}

public static boolean is_identical_tree(BinaryTreeNode root1, BinaryTreeNode root2) {
  if (root1 == null && root2 == null) {
    return true;
  }
  else if (root1 != null && root2 != null) {
    return ((root1.data == root2.data) &&
            is_identical_tree(root1.left, root2.left) &&
            is_identical_tree(root1.right, root2.right));
  }
  else {
    return false;
  }
}
}

Java

def level_order_traversal(root):
  result = ""
  #TODO: Write - Your - Code
  return result

import os, sys
utils_path = os.path.join('..', '..', '..', '..', 'problems', 'utils', 'python')
sys.path.append(utils_path)
from collections import deque

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    self.next = None
    self.parent = None


import random

def insert_binary_tree(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d <= parent.data:
    parent.right = pNew
  else:
    parent.left = pNew

  return root

def insert(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d < parent.data:
    parent.left = pNew
  else:
    parent.right = pNew

  return root

def find_in_bst(root, d):
  if root == None:
    return None

  if root.data == d:
    return root
  elif root.data > d:
    return find_in_bst(root.left, d)
  else:
    return find_in_bst(root.right, d)

# find node in inorder 
# works for both BST and binary tree
def find_node(root, d):
  if root == None:
    return

  if root.data == d:
    return root

  temp = find_node(root.left, d)
  if temp != None:
    return temp

  return find_node(root.right, d) 

def display_inorder(node):
  if node == None:
    return

  display_inorder(node.left)
  print(str(node.data), end = ", ")
  display_inorder(node.right)

def create_BST(arr):
  root = None
  for x in arr:
    root = insert(root, x)
  return root

def create_binary_tree(count):
  root = None
  for i in range(1, count):
    root = insert_binary_tree(root, random.randrange(1,100))
  return root

def create_random_BST(count):
  root = None;
  for i in range(1, count):
    root = insert(root, random.randrange(200, 300))
  return root

def bst_to_list_rec(root, lst):
  if root == None:
    return

  bst_to_list_rec(root.left, lst)
  lst.append(root.data)
  bst_to_list_rec(root.right, lst)

def bst_to_list(root):
  lst = []
  bst_to_list_rec(root, lst)
  return lst

def insert_at_head(head, data):
  newNode = LinkedListNode(data)
  newNode.next = head
  return newNode

def populate_parents_rec(root, parent):
  if root == None:
    return 
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)

def populate_parents(root):
  populate_parents_rec(root, None)

def display_level_order(root):
  if root == None:
    return
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    print(str(temp.data) + ",", end = " ")
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  print

def get_level_order(root):
  output = []
  if root == None:
    return output
  
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    output.append(temp.data)
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  return output

def get_inorder_helper(root, output):
  if root == None:
    return output

  output = get_inorder_helper(root.left, output)
  output.append(root.data)
  output = get_inorder_helper(root.right, output)
  
  return output

def get_inorder(root):
  output = []
  return get_inorder_helper(root, output)

def is_identical_tree(root1,root2):
  if root1 == None and root2 == None:
    return True

  if root1 != None and root2 != None and root1.data == root2.data: 
    return is_identical_tree(root1.left,root2.left) and is_identical_tree(root1.right,root2.right)

  return False

Python

let level_order_traversal = function(root) {
  var result = ""; 
   //TODO: Write - Your - Code
  return result;
};

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  display_level_order() {
    if (!this) {
      return;
    }
    let q = [];
    q.push(this);

    while (q.length > 0) {
      let temp = q.shift();
      console.log(temp.data + ",");

      for (let c in temp.children) {
        q.push(temp.children[c]);
      }
    }
  }
}

class BinaryTreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.next = null;
    this.parent = null;
  }
}

class LinkedListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
    this.arbitrary = null;
  }
}

let insert_binary_tree = function(root, d) {
  let pNew = new BinaryTreeNode(d);
  if (!root) {
    return pNew;
  }

  let parent = null;
  let pTemp = root
  while (pTemp) {
    let parent = pTemp;
    if (d < pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }
  if (d <= parent.data) {
    parent.right = pNew;
  } else {
    parent.left = pNew;
  }

  return root;
}

let insert = function(root, d) {
  let pNew = new BinaryTreeNode(d);
  if (!root) {
    return pNew;
  }

  let parent = null;
  let pTemp = root;
  while (pTemp) {
    parent = pTemp;
    if (d < pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }
  if (d < parent.data) {
    parent.left = pNew;
  } else {
    parent.right = pNew;
  }

  return root;
}

let find_in_bst = function(root, d) {
  if (!root) {
    return null;
  }

  if (root.data === d) {
    return root;
  } else if (root.data > d) {
    return find_in_bst(root.left, d);
  } else {
    return find_in_bst(root.right, d);
  }
}
// find node in inorder 
// works for both BST and binary tree
let find_node = function(root, d) {
  if (!root) {
    return;
  }

  if (root.data === d) {
    return root;
  }

  let temp = find_node(root.left, d);
  if (temp) {
    return temp;
  }

  return find_node(root.right, d);
}

let display_inorder = function(node) {
  if (!node) {
    return;
  }

  display_inorder(node.left);
  console.log(node.data);
  display_inorder(node.right);
}

let create_BST = function(arr) {
  let root = null;
  for (let x in arr) {
    root = insert(root, arr[x]);
  }
  return root;
}

let create_binary_tree = function(count) {
  let root = null;
  for (let i = 1; i < count; i++) {
    root = insert_binary_tree(root, Math.floor(Math.random() * 100 + 1));
  }
  return root;
}

let create_random_BST = function(count) {
  let root = null;
  for (let i = 1; i < count; i++) {
    root = insert(root, Math.floor(Math.random() * 100 + 200));
  }
  return root;
}

let bst_to_list_rec = function(root, lst) {
  if (!root) {
    return;
  }

  bst_to_list_rec(root.left, lst);
  lst.push(root.data);
  bst_to_list_rec(root.right, lst);
}

let bst_to_list = function(root) {
  let lst = [];
  bst_to_list_rec(root, lst);
  return lst;
}

let populate_parents_rec = function(root, parent) {
  if (!root) {
    return;
  }
  root.parent = parent;

  populate_parents_rec(root.left, root);
  populate_parents_rec(root.right, root);
}

let populate_parents = function(root) {
  populate_parents_rec(root, null);
}

let display_level_order = function(root) {
  if (!root) {
    return;
  }
  let q = [];
  q.push(root);
  let print_level = '';
  while (q.length > 0) {
    let temp = q.shift();
    print_level += temp.data + ",";
    if (temp.left) {
      q.push(temp.left);
    }
    if (temp.right) {
      q.push(temp.right)
    }
  }
  console.log(print_level);
}

let get_level_order = function(root) {
  let output = [];
  if (!root) {
    return output;
  }

  let q = [];
  q.push(root);

  while (q.length > 0) {
    let temp = q.shift();
    output.push(temp.data);
    if (temp.left) {
      q.push(temp.left);
    }
    if (temp.right) {
      q.push(temp.right);
    }
  }
  return output;
}

let get_inorder_helper = function(root, output) {
  if (!root) {
    return output;
  }

  output = get_inorder_helper(root.left, output);
  output.push(root.data);
  output = get_inorder_helper(root.right, output);

  return output;
}

let get_inorder = function(root) {
  let output = [];
  return get_inorder_helper(root, output);
}

let is_identical_tree = function(root1, root2) {
  if (!root1 && !root2) {
    return true;
  }

  if (root1 && root2 && root1.data === root2.data) {
    return is_identical_tree(root1.left, root2.left) && is_identical_tree(root1.right, root2.right);
  }

  return false;
}

JavaScript

def level_order_traversal(root)
  result = ""
  #TODO: Write - Your - Code
  return result
end

class BinaryTreeNode
  attr_accessor :data, :left, :right, :next, :parent, :count
  def initialize(data)
    @data = data
    @left = nil
    @right = nil
    @next = nil
    @parent = nil
    @count = -1
  end
end

def insert_binary_tree(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d <= parent.data)
    parent.right = pNew
  else
    parent.left = pNew
  end

  return root
end

def insert(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d < parent.data)
    parent.left = pNew
  else
    parent.right = pNew
  end

  return root
end

def find_in_bst(root, d)
  if (!root)
    return nil
  end

  if (root.data == d)
    return root
  elsif (root.data > d)
    return find_in_bst(root.left, d)
  else
    return find_in_bst(root.right, d)
  end
end

# find node in inorder
# works for both BST and binary tree
def find_node(root, d)
  if (!root)
    return
  end

  if (root.data == d)
    return root
  end

  temp = find_node(root.left, d)
  if (temp)
    return temp
  end

  return find_node(root.right, d)
end

def display_inorder(node)
  if (!node)
    return
  end

  display_inorder(node.left)
  print (node.data.to_s + ", ")
  display_inorder(node.right)
end
def create_BST(arr)
  root = nil
  arr.each do |x|
    root = insert(root, x)
  end
  return root
end

def create_binary_tree(count)
  root = nil
  (count-1).times do |i|
    root = insert_binary_tree(root, (rand * 100 + 1).floor)
  end
  return root
end

def create_random_BST(count)
  root = nil
  (count-1).times do |i|
    root = insert(root, (rand * 100 + 200).floor)
  end
  return root
end

def bst_to_list_rec(root, lst)
  if (!root)
    return
  end

  bst_to_list_rec(root.left, lst)
  lst.push(root.data)
  bst_to_list_rec(root.right, lst)
end

def bst_to_list(root)
  lst = []
  bst_to_list_rec(root, lst)
  return lst
end

def populate_parents_rec(root, parent)
  if (!root)
    return
  end
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)
end

def populate_parents(root)
  populate_parents_rec(root, nil)
end

def display_level_order(root)
  if (!root)
    return
  end
  q = []
  q.push(root)
  print_level = ''
  while (q.length > 0)
    temp = q.shift()
    print_level += temp.data.to_s + ","
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  print (print_level)
end

def get_level_order(root)
  output = []
  if (!root)
    return output
  end

  q = []
  q.push(root)

  while (q.length > 0)
    temp = q.shift()
    output.push(temp.data)
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  return output
end

def get_inorder_helper(root, output)
  if (!root)
    return output
  end

  output = get_inorder_helper(root.left, output)
  output.push(root.data)
  output = get_inorder_helper(root.right, output)

  return output
end

def get_inorder(root)
  output = []
  return get_inorder_helper(root, output)
end

def is_identical_tree(root1, root2)
  if (!root1 && !root2)
    return true
  end

  if (root1 && root2 && root1.data == root2.data)
    return is_identical_tree(root1.left, root2.left) && is_identical_tree(root1.right, root2.right)
  end

  return false
end

Ruby

// Using two queues
void level_order_traversal_1(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> queues[2];
  
  queue<BinaryTreeNode*>* current_queue = &queues[0];
  queue<BinaryTreeNode*>* next_queue = &queues[1];

  current_queue->push(root);
  int level_number = 0;

  while (!current_queue->empty()) {
    BinaryTreeNode* temp = current_queue->front();
    current_queue->pop();
    cout << temp->data << ",";

    if (temp->left != nullptr) {
      next_queue->push(temp->left);
    }

    if (temp->right != nullptr) {
      next_queue->push(temp->right);
    }

    if (current_queue->empty()) {
      cout << endl;
      ++level_number;
      current_queue = &queues[level_number % 2];
      next_queue = &queues[(level_number + 1) % 2];
    }
  }
  cout << endl;
}

int main(int argc, char* argv[]) {

  BinaryTreeNode* root = create_random_BST(15);
  level_order_traversal_1(root);
  cout << endl;
  cout << "Inorder = ";
  display_inorder(root);
  
}

class levelOrderTraversal{
    // Using two queues
  public static void level_order_traversal_1(
      BinaryTreeNode root) {

    if (root == null) {
      return;
    }
  
    ArrayList<Queue<BinaryTreeNode>> queues = 
      new ArrayList<Queue<BinaryTreeNode>>();

    queues.add(new ArrayDeque<BinaryTreeNode>());
    queues.add(new ArrayDeque<BinaryTreeNode>());

    Queue<BinaryTreeNode> current_queue = queues.get(0);
    Queue<BinaryTreeNode> next_queue = queues.get(1);

    current_queue.add(root);
    int level_number = 0;

    while (!current_queue.isEmpty()) {
      BinaryTreeNode temp = current_queue.poll();
      System.out.print(temp.data + ",");

      if (temp.left != null) {
        next_queue.add(temp.left);
      }

      if (temp.right != null) {
        next_queue.add(temp.right);
      }

      if (current_queue.isEmpty()) {
        System.out.println();
        ++level_number;
        current_queue = queues.get(level_number % 2);
        next_queue = queues.get((level_number + 1) % 2);
      }
    }
    System.out.println();
  }
  public static void main(String[] argv) {

    List<Integer> input = new ArrayList<Integer>();
    input.add(100);input.add(50);input.add(200);input.add(25);input.add(75);input.add(350);
    BinaryTreeNode root = BinaryTree.create_BST(input);
    level_order_traversal_1(root);
    System.out.println();


    System.out.print("Inorder = ");
    BinaryTree.display_inorder(root);

  }
}  

# Using two queues
def level_order_traversal_1(root):
  if root == None:
    return

  queues = [deque(), deque()]

  current_queue = queues[0]
  next_queue = queues[1]
  
  current_queue.append(root)
  level_number = 0

  while current_queue:
    temp = current_queue.popleft()
    print(str(temp.data) , end = " ")

    if temp.left != None:
      next_queue.append(temp.left)

    if temp.right != None:
      next_queue.append(temp.right)

    if not current_queue:
      print()
      level_number += 1
      current_queue = queues[level_number % 2]
      next_queue = queues[(level_number + 1) % 2]
  print()
  
arr = [100,50,200,25,75,350]
root = create_BST(arr)
print("InOrder Traversal:", end = "")
display_inorder(root)
print("\nLevel Order Traversal:\n", end = "")
level_order_traversal_1(root)

# Using two queues
def level_order_traversal_1(root)
  if (!root)
    return
  end

  queues = [ [], [] ]
  current_queue = queues[0]
  next_queue = queues[1]

  current_queue.push(root)
  level_number = 0

  while (current_queue.length > 0)
    temp = current_queue.shift()
    print (temp.data.to_s + " ")
    if (temp.left)
      next_queue.push(temp.left)
    end

    if (temp.right)
      next_queue.push(temp.right)
    end

    if (current_queue.length == 0)
      puts
      level_number+=1
      current_queue = queues[level_number % 2]
      next_queue = queues[(level_number + 1) % 2]
    end
  end
  puts
end

def main()
  arr = [100,50,200,25,75,350]
  root = create_BST(arr)
  print "\nIn Order Traversal: "
  display_inorder(root)
  #display_level_order(root)
  print "\nLevel Order Traversal1: \n"
  level_order_traversal_1(root)
end

main()

## Solution Explanation
### Runtime Complexity
The runtime complexity of this solution is linear, O(n).

### Memory Complexity 
The memory complexity of this solution is linear, O(n).

<br>

### Solution Breakdown
Here, you are using two queues: `current_queue` and `next_queue`. You push the nodes in both queues alternately based on the current level number.

You’ll dequeue nodes from the `current_queue`, print the node’s data, and enqueue the node’s children to the `next_queue`. Once the `current_queue` becomes empty, you have processed all nodes for the current `level_number`. To indicate the new level, print a line break (’\n’), swap the two queues, and continue with the above-mentioned logic.

After printing the leaf nodes from the `current_queue`, swap `current_queue` and `next_queue`. Since the `current_queue` would be empty, you can terminate the loop.

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given the root of a binary tree, display the node values at each level.

Level Order Traversal of Binary Tree

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown