MIRRORS AND TREES

Mirrors and Trees

 

 

QUS:

Given a binary tree in a two dimensional plane which has both side covered by mirrors. As this is a 2D dimensional image, we define our print function to print only those nodes whose reflection is showing on one of the mirrors, first we print the value of the nodes with reflections appearing on the right mirror and then print the values of the ones appearing on the left and we don't need to print the same node again which has already been printed on right mirror, so each node is going to printed only once even in a case where the node has a reflection on both mirrors.
Suppose in the array representation of binary trees, we fill the positions where the left or right child of a node does not exist with 0s.
So the tree

     3

    / 

   2

  /

 1  

will look in array representation as 3 2 0 1 0 0 0 0 0 0 0 0 0 0 0 i.e.

         3
       /   \
      2     0
     / \    / \
    1   0  0   0
   / \ / \ / \ / \
  0  0 0 0 0 0 0  0

and the tree

    

        1 

       / \  
      2   3

will look in the array representation as 1 2 3 0 0 0 0 i.e.

         1

       /  \  
      2    3

     / \   / \  
    0   0  0  0 

ANS

program:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
void main()
{
long int a[20][100],t,s,i,j,l,b=1,k=0;
printf("T=");
    scanf("%ld",&t);

        for(i=1;i<=t;i++)
        {
printf("size of array \n");
                scanf("%ld",&s);
Printf("array \n");
                for(j=1;j<=s;j++)
                {
                   scanf("%ld",&a[i][j]);
                }
        }
       for(i=1;i<=t;i++)
        {

            for(j=1;j<=s;j++)
            {
            k=(2*k)+1;
            if(a[i][k]!=0) printf("%ld \n",a[i][k]);
            }
            for(j=1;j<=s;j++){
            b=2*b;
           if(a[i][b]!=0) printf("%ld \n",a[i][b]);}
           k=0;
           b=1;
           printf("\n");
        }
}

----------------------------------------------------------------------------------
here for every ith node, it's left child is at (2 * i) th and right child at (2 * i + 1)th position.
Input:
First line contains number of test cases T. First line of each test case contains a single integer N,size of array and second line contains the tree in array representation form as mentioned above.
Output:
For each test case, first print the value of the nodes with reflections appearing on the right mirror and then print values of the ones appearing on the left and don't need to print the same node again which has already been printed on right mirror, so each node is going to printed only once even in a case where the node has a reflection on both mirrors.
Constraints:
1<=T<=20
3<=N<=2^18
Note:
The value of N will always be greater than equal to 3 and will be in the form (2^k-1) where k>=2.
Last level of the tree is filled with all 0s.
Assume array indices start from 1.

---

Sample Input 

2
7
1 2 3 0 0 0 0
7
1 3 0 0 0 0 0

Sample Output  1
3
2

1
3

____________________________________________________________________________