using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Node a=new Node(10);

        Node b=new Node(20);

        Node c=new Node(30);

        Node d=new Node(40);

        Node e=new Node(50);

        Node f=new Node(60);

        a.left=b;

        a.right=c;

        b.left=d;

        b.right=e;

        c.left=f;

        //CopyBinaryTreeRecursive(a);

        CopyBinaryTreeIterative(a);

        //Console.WriteLine("Hello");

    }

    public static Node CopyBinaryTreeRecursive(Node root){

        if(root==null) return null;

        Node newNode=new Node(root.data);

        Console.WriteLine(newNode.data.ToString());

        newNode.left=CopyBinaryTreeRecursive(root.left);

        newNode.right=CopyBinaryTreeRecursive(root.right);

        return newNode;

    }

    public static Node CopyBinaryTreeIterative(Node root){

        if(root==null) return null;

        Queue<Node> q=new Queue<Node>();

        Queue<Node> q1=new Queue<Node>();

        q.Enqueue(root);

        q1.Enqueue(new Node(root.data));

        Node result=q1.Peek();

        while(q.Count>0){

            Node current=q.Peek();

            //Console.WriteLine(q1.Peek().data.ToString());

            if(current.left!=null) 

            {

                q1.Peek().left=new Node(current.left.data);

                q1.Enqueue(q1.Peek().left);

                q.Enqueue(current.left);

            }

            if(current.right!=null) 

            {

                q1.Peek().right=new Node(current.right.data); 

                q1.Enqueue(q1.Peek().right);

                q.Enqueue(current.right);

            }

            Console.WriteLine(q1.Peek().data.ToString());

            q.Dequeue();

            q1.Dequeue();

        }

        return result;

    }

}

​

public class Node{

    public int data;

    public Node left;

    public Node right;

    public Node(int val){

        data=val;

    }

}