TechInsiderStory

Create Own HashMap

  
 
package linklist.hashmap;
 
class Entry<K, V> {
 
    private K key;
    private V value;
    private Entry<K, V> next;
 
    public Entry(K key, V value, Entry<K, V> next){
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    public K getKey() {
        return key;
    }
 
    public void setKey(K key) {
        this.key = key;
    }
 
    public V getValue() {
        return value;
    }
 
    public void setValue(V value) {
        this.value = value;
    }
 
    public Entry getNext() {
        return next;
    }
 
    public void setNext(Entry<K, V> next) {
        this.next = next;
    }
}
 
class CustomHashMap<K, V> {
    private int capacity = 16; //Initial default capacity
 
    private Entry<K, V>[] table; //Array of Entry object
 
    public CustomHashMap(){
        table = new Entry[capacity];
    }
 
    public CustomHashMap(int capacity){
        this.capacity = capacity;
        table = new Entry[capacity];
    }
 
    public void put(K key, V value){
        int index = index(key);
        Entry newEntry = new Entry(key, value, null);
        if(table[index] == null){
            table[index] = newEntry;
        }else {
            Entry<K, V> previousNode = null;
            Entry<K, V> currentNode = table[index];
            while(currentNode != null){
                if(currentNode.getKey().equals(key)){
                    currentNode.setValue(value);
                    break;
                }
                previousNode = currentNode;
                currentNode = currentNode.getNext();
            }
            if(previousNode != null)
                previousNode.setNext(newEntry);
        }
    }
 
    public V get(K key){
        V value = null;
        int index = index(key);
        Entry<K, V> entry = table[index];
        while (entry != null){
            if(entry.getKey().equals(key)) {
                value = entry.getValue();
                break;
            }
            entry = entry.getNext();
        }
        return value;
    }
 
    public void remove(K key){
        int index = index(key);
        Entry previous = null;
        Entry entry = table[index];
        while (entry != null){
            if(entry.getKey().equals(key)){
                if(previous == null){
                    entry = entry.getNext();
                    table[index] = entry;
                    return;
                }else {
                    previous.setNext(entry.getNext());
                    return;
                }
            }
            previous = entry;
            entry = entry.getNext();
        }
    }
 
    public void display(){
        for(int i = 0; i < capacity; i++){
            if(table[i] != null){
                Entry<K, V> currentNode = table[i];
                while (currentNode != null){
                    System.out.println(String.format("Key is %s and value is %s", currentNode.getKey(), currentNode.getValue()));
                    currentNode = currentNode.getNext();
                }
            }
        }
    }
 
    private int index(K key){
        if(key == null){
            return 0;
        }
        return Math.abs(key.hashCode() % capacity);
    }
}
 
public class HashMapRunner {
    public static void main(String[] args) {
        CustomHashMap<Integer, String> map = new CustomHashMap<Integer, String>();
        System.out.println("Going to add entries in map");
        map.put(null, "Nothing");
        map.put(1, "ETC");
        map.put(2, "John");
        System.out.println("Displaying all the entry in map");
        map.display();
        System.out.println("Removing the entry with key 2");
        map.remove(2);
        map.display();
        System.out.println("Adding duplicate key 1 in map");
        map.put(1, "CSE");
        map.put(2, "John again");
        System.out.println("Displaying all the entry in map again");
        map.display();
        System.out.println("Adding entry with key 17 in map");
        map.put(17, "CS");
        map.display();
    }
}

Sub-Matrix With All 1s

  
 
public class SubMatrix {
    static void getMaxSubSquare(int M[][])
    {
        int i, j;
        int R = M.length; // no of rows in M[][]
        int C = M[0].length; // no of columns in M[][]
        int S[][] = new int[R][C];
 
        int maxS, maxI, maxJ;
 
        /* Set first column of S[][]*/
        for (i = 0; i < R; i++)
            S[i][0] = M[i][0];
 
        /* Set first row of S[][]*/
        for (j = 0; j < C; j++)
            S[0][j] = M[0][j];
 
        /* Construct other entries of S[][]*/
        for (i = 1; i < R; i++) {
            for (j = 1; j < C; j++) {
                if (M[i][j] == 1)
                    S[i][j] = Math.min(
                            S[i][j - 1],
                            Math.min(S[i - 1][j],
                                    S[i - 1][j - 1]))
                            + 1;
                else
                    S[i][j] = 0;
            }
        }
 
        /* Find the maximum entry, and indexes of maximum
           entry in S[][] */
        maxS = S[0][0];
        maxI = 0;
        maxJ = 0;
        for (i = 0; i < R; i++) {
            for (j = 0; j < C; j++) {
                if (maxS < S[i][j]) {
                    maxS = S[i][j];
                    maxI = i;
                    maxJ = j;
                }
            }
        }
 
        System.out.println("Maximum size sub-matrix is: ");
        for (i = maxI; i > maxI - maxS; i--) {
            for (j = maxJ; j > maxJ - maxS; j--) {
                System.out.print(M[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int M[][]
                = { { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 },
                { 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 0 },
                { 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0 } };
 
        getMaxSubSquare(M);
    }
        //Time Complexity: O(m*n)
    // where m is the number of rows and n is the number of columns in the given matrix.
    //Auxiliary Space: O(m*n)
    // where m is the number of rows and n is the number of columns in the given matrix.
}

Link-List-Palindrome

  
 
 
public class LinkListPalindrome {
    Node head; // head of list
    Node slp, ftp, secHalf;
 
    /* Linked list Node*/
    class Node {
        char data;
        Node next;
 
        Node(char d)
        {
            data = d;
            next = null;
        }
    }
 
    /* Function to check if given linked list is
       palindrome or not */
    boolean isPalindrome(Node head)
    {
        slp = head;
        ftp = head;
        Node prev_of_slow_ptr = head;
        Node midnode = null; // To handle odd size list
        boolean res = true; // initialize result
 
        if (head != null && head.next != null) {
            /* Get the middle of the list. Move slow_ptr by
               1 and fast_ptr by 2, slow_ptr will have the
               middle node */
            while (ftp != null
                    && ftp.next != null) {
                ftp = ftp.next.next;
 
                /*We need previous of the slow_ptr for
                  linked lists  with odd elements */
                prev_of_slow_ptr = slp;
                slp = slp.next;
            }
 
            /* fast_ptr would become NULL when there are
               even elements in the list and not NULL for
               odd elements. We need to skip the middle node
               for odd case and store it somewhere so that
               we can restore the original list */
            if (ftp != null) {
                midnode = slp;
                slp = slp.next;
            }
 
            // Now reverse the second half and compare it
            // with first half
            secHalf = slp;
            prev_of_slow_ptr.next
                    = null; // NULL terminate first half
            reverse(); // Reverse the second half
            res = compareLists(head,
                    secHalf); // compare
 
            /* Construct the original list back */
            reverse(); // Reverse the second half again
 
            if (midnode != null) {
                // If there was a mid node (odd size case)
                // which was not part of either first half
                // or second half.
                prev_of_slow_ptr.next = midnode;
                midnode.next = secHalf;
            }
            else
                prev_of_slow_ptr.next = secHalf;
        }
        return res;
    }
 
    /* Function to reverse the linked list  Note that this
       function may change the head */
    void reverse()
    {
        Node prev = null;
        Node current = secHalf;
        Node next;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        secHalf = prev;
    }
 
    /* Function to check if two input lists have same data*/
    boolean compareLists(Node head1, Node head2)
    {
        Node temp1 = head1;
        Node temp2 = head2;
 
        while (temp1 != null && temp2 != null) {
            if (temp1.data == temp2.data) {
                temp1 = temp1.next;
                temp2 = temp2.next;
            }
            else
                return false;
        }
 
        /* Both are empty return 1*/
        if (temp1 == null && temp2 == null)
            return true;
 
        /* Will reach here when one is NULL
           and other is not */
        return false;
    }
 
    /* Push a node to linked list. Note that this function
       changes the head */
    public void push(char new_data)
    {
        /* Allocate the Node &
           Put in the data */
        Node new_node = new Node(new_data);
 
        /* link the old list of the new one */
        new_node.next = head;
 
        /* Move the head to point to new Node */
        head = new_node;
    }
 
    // A utility function to print a given linked list
    void printList(Node ptr)
    {
        while (ptr != null) {
            System.out.print(ptr.data + "->");
            ptr = ptr.next;
        }
        System.out.println("NULL");
    }
 
    /* Driver program to test the above functions */
    public static void main(String[] args)
    {
 
        /* Start with the empty list */
        LinkListPalindrome llist = new LinkListPalindrome();
 
        char str[] = { 'a', 'b', 'a', 'c', 'a', 'b', 'a' };
        String string = new String(str);
        for (int i = 0; i < 7; i++) {
            llist.push(str[i]);
        }
        if (llist.isPalindrome(llist.head) != false) {
            System.out.println("Is Palindrome");
            System.out.println("");
        }
        else {
            System.out.println("Not Palindrome");
            System.out.println("");
        }
    }
}

Tree-Traverse-Order-Level-Frame

  
 
 
 
import java.util.*;
 
// structure of the node of the binary tree
class Node{
    int data;
    Node left;
    Node right;
    public Node(int data)
    {
        this.data=data;
    }
}
public class TraversTreeAndFrame {
 
    static ArrayList<Object[]> traversal;
 
    // function to traverse the binary
    // tree in the level order fashion
    public static void levelOrderTraversal(Node root)
    {
        // current node is marked as the root node
        Node curr=root;
        int level=0;
        // loop to traverse the binary tree until the current node
        // is not null
        while(curr!=null)
        {
            // if left child is null, print the
            // current node data and update the
            // current pointer to right child.
            if(curr.left==null)
            {
                // return the current node with
                // its level
                traversal.add(new Object[]{curr,new Integer(level)});
                curr=curr.right;
                if(curr!=null)
                {
                    level++;
                }else
                    level--;
            }
            else{
                // find the inorder predecessor
                Node prev=curr.left;
                int toUp=0;
 
                // loop to find the right most
                // node of the left child of the current node
                while(prev.right!=null && prev.right!=curr)
                {
                    prev=prev.right;
                    toUp++;
                }
                // If the right child of inorder
                // predecessor already points to
                // the current node, update the
                // current with it's right child
                if(prev.right==curr)
                {
                    prev.right=null;
                    curr=curr.right;
                    level-=toUp+1;
                }
                // else If right child doesn't
                // point to the current node,
                // then print this node's data
                // and update the right child
                // pointer with the current node
                // and update the current with
                // it's left child
                else{
                    traversal.add(new Object[]{curr,new Integer(level)});
                    prev.right=curr;
                    curr=curr.left;
                    level++;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        // create a binary tree
        Node root=new Node(5);
        root.left=new Node(2);
        root.right=new Node(3);
        root.left.right=new Node(6);
        root.right.left=new Node(7);
        root.right.right=new Node(8);
        traversal=new ArrayList<>();
 
        // traverse the tree in level order traversal
        levelOrderTraversal(root);
 
        // find the height of the tree
        int h=0;
        for(Object[] i:traversal)
        {
            h=Math.max(h,(int)i[1]+1);
        }
 
        // print the date of nodes at each level
        for(int i = 0; i<h; i++){
            for(Object[] j : traversal){
                if((int)j[1] == i){
 
                    System.out.print(((Node)j[0]).data+" ");
                }
            }
            System.out.println();
        }
    }
  //Time Complexity: As in the above approach, every node is
    // touched at max twice due to which the time complexity is O(N),
    // where N is the number of nodes.
    //Auxiliary Space: As in the above approach,
    // there is no extra space used due to which auxiliary space used will be O(1) 
  
    
}

Tree-Traverse-Order-Level-Queue

  
 
import java.util.LinkedList;
import java.util.Queue;
 
 
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = null;
        right = null;
    }
}
class LevelOrderQueue {
 
    Node root;
 
    void printLevelOrder()
    {
       Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
 
            Node tempNode = queue.poll();
            System.out.print(tempNode.data + " ");
            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }
    }
 
    public static void main(String args[])
    {
        LevelOrderQueue tree_level = new LevelOrderQueue();
        tree_level.root = new Node(1);
        tree_level.root.left = new Node(2);
        tree_level.root.right = new Node(3);
        tree_level.root.left.left = new Node(4);
        tree_level.root.left.right = new Node(5);
 
        tree_level.printLevelOrder();
    }
 
//Firstly we insert the root into the queue and iterate over
//the queue until the queue is empty.
//In every iteration, we will pop from the top of
// the queue and print the value at the top of the queue.
//Then, add its left and right nodes to the end of the queue
// Time Complexity: O(N) where n is the number of nodes in the binary tree.
//Space Complexity: O(N) where n is the number of nodes in the binary tree.
}



	package linklist.hashmap;

	class Entry<K, V> {

	private K key;
	private V value;
	private Entry<K, V> next;

	public Entry(K key, V value, Entry<K, V> next){
	this.key = key;
	this.value = value;
	this.next = next;
	}

	public K getKey() {
	return key;
	}

	public void setKey(K key) {
	this.key = key;
	}

	public V getValue() {
	return value;
	}

	public void setValue(V value) {
	this.value = value;
	}

	public Entry getNext() {
	return next;
	}

	public void setNext(Entry<K, V> next) {
	this.next = next;
	}
	}

	class CustomHashMap<K, V> {
	private int capacity = 16; //Initial default capacity

	private Entry<K, V>[] table; //Array of Entry object

	public CustomHashMap(){
	table = new Entry[capacity];
	}

	public CustomHashMap(int capacity){
	this.capacity = capacity;
	table = new Entry[capacity];
	}

	public void put(K key, V value){
	int index = index(key);
	Entry newEntry = new Entry(key, value, null);
	if(table[index] == null){
	table[index] = newEntry;
	}else {
	Entry<K, V> previousNode = null;
	Entry<K, V> currentNode = table[index];
	while(currentNode != null){
	if(currentNode.getKey().equals(key)){
	currentNode.setValue(value);
	break;
	}
	previousNode = currentNode;
	currentNode = currentNode.getNext();
	}
	if(previousNode != null)
	previousNode.setNext(newEntry);
	}
	}

	public V get(K key){
	V value = null;
	int index = index(key);
	Entry<K, V> entry = table[index];
	while (entry != null){
	if(entry.getKey().equals(key)) {
	value = entry.getValue();
	break;
	}
	entry = entry.getNext();
	}
	return value;
	}

	public void remove(K key){
	int index = index(key);
	Entry previous = null;
	Entry entry = table[index];
	while (entry != null){
	if(entry.getKey().equals(key)){
	if(previous == null){
	entry = entry.getNext();
	table[index] = entry;
	return;
	}else {
	previous.setNext(entry.getNext());
	return;
	}
	}
	previous = entry;
	entry = entry.getNext();
	}
	}

	public void display(){
	for(int i = 0; i < capacity; i++){
	if(table[i] != null){
	Entry<K, V> currentNode = table[i];
	while (currentNode != null){
	System.out.println(String.format("Key is %s and value is %s", currentNode.getKey(), currentNode.getValue()));
	currentNode = currentNode.getNext();
	}
	}
	}
	}

	private int index(K key){
	if(key == null){
	return 0;
	}
	return Math.abs(key.hashCode() % capacity);
	}
	}

	public class HashMapRunner {
	public static void main(String[] args) {
	CustomHashMap<Integer, String> map = new CustomHashMap<Integer, String>();
	System.out.println("Going to add entries in map");
	map.put(null, "Nothing");
	map.put(1, "ETC");
	map.put(2, "John");
	System.out.println("Displaying all the entry in map");
	map.display();
	System.out.println("Removing the entry with key 2");
	map.remove(2);
	map.display();
	System.out.println("Adding duplicate key 1 in map");
	map.put(1, "CSE");
	map.put(2, "John again");
	System.out.println("Displaying all the entry in map again");
	map.display();
	System.out.println("Adding entry with key 17 in map");
	map.put(17, "CS");
	map.display();
	}
	}



	public class SubMatrix {
	static void getMaxSubSquare(int M[][])
	{
	int i, j;
	int R = M.length; // no of rows in M[][]
	int C = M[0].length; // no of columns in M[][]
	int S[][] = new int[R][C];

	int maxS, maxI, maxJ;

	/* Set first column of S[][]*/
	for (i = 0; i < R; i++)
	S[i][0] = M[i][0];

	/* Set first row of S[][]*/
	for (j = 0; j < C; j++)
	S[0][j] = M[0][j];

	/* Construct other entries of S[][]*/
	for (i = 1; i < R; i++) {
	for (j = 1; j < C; j++) {
	if (M[i][j] == 1)
	S[i][j] = Math.min(
	S[i][j - 1],
	Math.min(S[i - 1][j],
	S[i - 1][j - 1]))
	+ 1;
	else
	S[i][j] = 0;
	}
	}

	/* Find the maximum entry, and indexes of maximum
	entry in S[][] */
	maxS = S[0][0];
	maxI = 0;
	maxJ = 0;
	for (i = 0; i < R; i++) {
	for (j = 0; j < C; j++) {
	if (maxS < S[i][j]) {
	maxS = S[i][j];
	maxI = i;
	maxJ = j;
	}
	}
	}

	System.out.println("Maximum size sub-matrix is: ");
	for (i = maxI; i > maxI - maxS; i--) {
	for (j = maxJ; j > maxJ - maxS; j--) {
	System.out.print(M[i][j] + " ");
	}
	System.out.println();
	}
	}

	// Driver program
	public static void main(String[] args)
	{
	int M[][]
	= { { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 },
	{ 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 0 },
	{ 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0 } };

	getMaxSubSquare(M);
	}
	//Time Complexity: O(m*n)
	// where m is the number of rows and n is the number of columns in the given matrix.
	//Auxiliary Space: O(m*n)
	// where m is the number of rows and n is the number of columns in the given matrix.
	}




	public class LinkListPalindrome {
	Node head; // head of list
	Node slp, ftp, secHalf;

	/* Linked list Node*/
	class Node {
	char data;
	Node next;

	Node(char d)
	{
	data = d;
	next = null;
	}
	}

	/* Function to check if given linked list is
	palindrome or not */
	boolean isPalindrome(Node head)
	{
	slp = head;
	ftp = head;
	Node prev_of_slow_ptr = head;
	Node midnode = null; // To handle odd size list
	boolean res = true; // initialize result

	if (head != null && head.next != null) {
	/* Get the middle of the list. Move slow_ptr by
	1 and fast_ptr by 2, slow_ptr will have the
	middle node */
	while (ftp != null
	&& ftp.next != null) {
	ftp = ftp.next.next;

	/*We need previous of the slow_ptr for
	linked lists with odd elements */
	prev_of_slow_ptr = slp;
	slp = slp.next;
	}

	/* fast_ptr would become NULL when there are
	even elements in the list and not NULL for
	odd elements. We need to skip the middle node
	for odd case and store it somewhere so that
	we can restore the original list */
	if (ftp != null) {
	midnode = slp;
	slp = slp.next;
	}

	// Now reverse the second half and compare it
	// with first half
	secHalf = slp;
	prev_of_slow_ptr.next
	= null; // NULL terminate first half
	reverse(); // Reverse the second half
	res = compareLists(head,
	secHalf); // compare

	/* Construct the original list back */
	reverse(); // Reverse the second half again

	if (midnode != null) {
	// If there was a mid node (odd size case)
	// which was not part of either first half
	// or second half.
	prev_of_slow_ptr.next = midnode;
	midnode.next = secHalf;
	}
	else
	prev_of_slow_ptr.next = secHalf;
	}
	return res;
	}

	/* Function to reverse the linked list Note that this
	function may change the head */
	void reverse()
	{
	Node prev = null;
	Node current = secHalf;
	Node next;
	while (current != null) {
	next = current.next;
	current.next = prev;
	prev = current;
	current = next;
	}
	secHalf = prev;
	}

	/* Function to check if two input lists have same data*/
	boolean compareLists(Node head1, Node head2)
	{
	Node temp1 = head1;
	Node temp2 = head2;

	while (temp1 != null && temp2 != null) {
	if (temp1.data == temp2.data) {
	temp1 = temp1.next;
	temp2 = temp2.next;
	}
	else
	return false;
	}

	/* Both are empty return 1*/
	if (temp1 == null && temp2 == null)
	return true;

	/* Will reach here when one is NULL
	and other is not */
	return false;
	}

	/* Push a node to linked list. Note that this function
	changes the head */
	public void push(char new_data)
	{
	/* Allocate the Node &
	Put in the data */
	Node new_node = new Node(new_data);

	/* link the old list of the new one */
	new_node.next = head;

	/* Move the head to point to new Node */
	head = new_node;
	}

	// A utility function to print a given linked list
	void printList(Node ptr)
	{
	while (ptr != null) {
	System.out.print(ptr.data + "->");
	ptr = ptr.next;
	}
	System.out.println("NULL");
	}

	/* Driver program to test the above functions */
	public static void main(String[] args)
	{

	/* Start with the empty list */
	LinkListPalindrome llist = new LinkListPalindrome();

	char str[] = { 'a', 'b', 'a', 'c', 'a', 'b', 'a' };
	String string = new String(str);
	for (int i = 0; i < 7; i++) {
	llist.push(str[i]);
	}
	if (llist.isPalindrome(llist.head) != false) {
	System.out.println("Is Palindrome");
	System.out.println("");
	}
	else {
	System.out.println("Not Palindrome");
	System.out.println("");
	}
	}
	}





	import java.util.*;

	// structure of the node of the binary tree
	class Node{
	int data;
	Node left;
	Node right;
	public Node(int data)
	{
	this.data=data;
	}
	}
	public class TraversTreeAndFrame {

	static ArrayList<Object[]> traversal;

	// function to traverse the binary
	// tree in the level order fashion
	public static void levelOrderTraversal(Node root)
	{
	// current node is marked as the root node
	Node curr=root;
	int level=0;
	// loop to traverse the binary tree until the current node
	// is not null
	while(curr!=null)
	{
	// if left child is null, print the
	// current node data and update the
	// current pointer to right child.
	if(curr.left==null)
	{
	// return the current node with
	// its level
	traversal.add(new Object[]{curr,new Integer(level)});
	curr=curr.right;
	if(curr!=null)
	{
	level++;
	}else
	level--;
	}
	else{
	// find the inorder predecessor
	Node prev=curr.left;
	int toUp=0;

	// loop to find the right most
	// node of the left child of the current node
	while(prev.right!=null && prev.right!=curr)
	{
	prev=prev.right;
	toUp++;
	}
	// If the right child of inorder
	// predecessor already points to
	// the current node, update the
	// current with it's right child
	if(prev.right==curr)
	{
	prev.right=null;
	curr=curr.right;
	level-=toUp+1;
	}
	// else If right child doesn't
	// point to the current node,
	// then print this node's data
	// and update the right child
	// pointer with the current node
	// and update the current with
	// it's left child
	else{
	traversal.add(new Object[]{curr,new Integer(level)});
	prev.right=curr;
	curr=curr.left;
	level++;
	}
	}
	}
	}
	public static void main(String[] args)
	{
	// create a binary tree
	Node root=new Node(5);
	root.left=new Node(2);
	root.right=new Node(3);
	root.left.right=new Node(6);
	root.right.left=new Node(7);
	root.right.right=new Node(8);
	traversal=new ArrayList<>();

	// traverse the tree in level order traversal
	levelOrderTraversal(root);

	// find the height of the tree
	int h=0;
	for(Object[] i:traversal)
	{
	h=Math.max(h,(int)i[1]+1);
	}

	// print the date of nodes at each level
	for(int i = 0; i<h; i++){
	for(Object[] j : traversal){
	if((int)j[1] == i){

	System.out.print(((Node)j[0]).data+" ");
	}
	}
	System.out.println();
	}
	}
	//Time Complexity: As in the above approach, every node is
	// touched at max twice due to which the time complexity is O(N),
	// where N is the number of nodes.
	//Auxiliary Space: As in the above approach,
	// there is no extra space used due to which auxiliary space used will be O(1)


	}



	import java.util.LinkedList;
	import java.util.Queue;


	class Node {
	int data;
	Node left, right;

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

	Node root;

	void printLevelOrder()
	{
	Queue<Node> queue = new LinkedList<Node>();
	queue.add(root);
	while (!queue.isEmpty()) {

	Node tempNode = queue.poll();
	System.out.print(tempNode.data + " ");
	if (tempNode.left != null) {
	queue.add(tempNode.left);
	}
	if (tempNode.right != null) {
	queue.add(tempNode.right);
	}
	}
	}

	public static void main(String args[])
	{
	LevelOrderQueue tree_level = new LevelOrderQueue();
	tree_level.root = new Node(1);
	tree_level.root.left = new Node(2);
	tree_level.root.right = new Node(3);
	tree_level.root.left.left = new Node(4);
	tree_level.root.left.right = new Node(5);

	tree_level.printLevelOrder();
	}

	//Firstly we insert the root into the queue and iterate over
	//the queue until the queue is empty.
	//In every iteration, we will pop from the top of
	// the queue and print the value at the top of the queue.
	//Then, add its left and right nodes to the end of the queue
	// Time Complexity: O(N) where n is the number of nodes in the binary tree.
	//Space Complexity: O(N) where n is the number of nodes in the binary tree.
	}