In this HackerEarth Gandhi Tree March problem solution, Gandhijee is interested in building a human tree. He defined a human node as follows :

Person_Id = English alphabet {a...z} .
Person_Chain_Definition = Person_Id ( Person_Chain_Definition Person_Chain_Definition )
For example :
a( b(..) c( d( . e(..) ) f( . . ) ) ) refers to a human tree having a as the root human, whose chain links are are b and c, (spaces here are for clarity, input file has no spaces).

Note: After every Person_Id there is necessarily an opening parenthesis ( that starts the definition of the sub-tree under the person. For empty(NULL) human nodes, there is a '.' character.
Now, Gandhijee figures out the tree as follows :
Step 1: He writes root human root id in column 0.
Step 2: Then he writes the left link's person id in 1 column to the left and the right link's person id in 1 column to the right.
He continues writing the subtree, in a way that, for an id written in column C, its left link's id is written in column C-1 and the right link's id is written in column C+1.

Now, Gandhijee wants to know the ids of people standing in a particular column C in lexicographically sorted order.
You are provided with column number C and the Tree definition string S. Gandhijee is very busy and hence he wants you to help him.


HackerEarth Gandhi Tree March problem solution


HackerEarth Gandhi Tree March problem solution.

#include<string>
#include<vector>
#include<cstdio>
#include<sstream>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;

int pos;
string S;
vector<char> L[10001], R[10001];

void buildTree(int C)
{
if(S[pos]!='.')
{
if(abs(C)<=10000)
{
if(C>=0) L[C].push_back(S[pos]);
else R[-C].push_back(S[pos]);
}
pos+=2;
buildTree(C-1);
buildTree(C+1);
}
pos++;
}

int main()
{
int i, T, C, Size;
cin>>T;
while(T--)
{
pos=0;
cin>>C>>S;
for(i=0; i<=10000; i++) L[i].clear(), R[i].clear();

buildTree(0);

if(C>=0)
{
if(Size=L[C].size())
{
sort(L[C].begin(), L[C].end());
for(i=0; i<Size; i++) cout<<L[C][i];
cout<<endl;
}
else cout<<"Common Gandhijee!\n";
}
else
{
if(Size=R[-C].size())
{
sort(R[-C].begin(),R[-C].end());
for(i=0; i<Size; i++)cout<<R[-C][i];
cout<<endl;
}
else cout<<"Common Gandhijee!\n";
}
}
return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define maxc (1000)
#define assn(n,a,b) assert(n>=a && n<=b)
string arr[2*(maxc) + 100];
int a;
string str;
void process(int b)
{
if(str[a]!='.')
{
if(abs(b)<=maxc)
arr[b+maxc]+=str[a];
a+=2;
process(b-1);
process(b+1);
}
a++;
}
int main()
{
int t;
cin >> t;
while(t--)
{
int c,i,j,n;
a=0;
for(i=0; i<2*maxc + 100; i++)
arr[i]="";
cin >> c >> str;
n=str.length();
assn(c,-1*maxc,maxc);
process(0);
sort(arr[c+maxc].begin(),arr[c+maxc].end());
if(arr[c+maxc].size())
cout << arr[c+maxc] << endl;
else cout << "Common Gandhijee!" << endl;
}
return 0;
}