# HackerEarth Restoring trees problem solution

In this HackerEarth Restoring trees problem solution You are given the start and finish times of a DFS (Depth-first search) traversal of the vertices that are available in a rooted tree. Your task is to restore the tree.

## HackerEarth Restoring trees problem solution

`#include<bits/stdc++.h>using namespace std;const int N = 300005;int n, st[N], fn[N], rev[N], P[N];void Solve(int v){    int nw = st[v] + 1;    int u = rev[nw];    for (; nw < fn[v]; nw = fn[u], u = rev[nw])        P[u] = v, Solve(u);}int main(){    scanf("%d", &n);    for (int i = 1; i <= n; i++)        scanf("%d", &st[i]), rev[st[i]] = i;    for (int i = 1; i <= n; i++)        scanf("%d", &fn[i]);    Solve(rev[0]);    for (int i = 1; i <= n; i++)        printf("%d ", P[i]);    printf("\n");    return (0);}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 3e5 + 14;int n, st[maxn], en[maxn], per[maxn], ans[maxn];int main(){    ios::sync_with_stdio(0), cin.tie(0);    cin >> n;    for(int i = 0; i < n; i++)        cin >> st[i];    for(int i = 0; i < n; i++)        cin >> en[i];    iota(per, per + n, 0);    sort(per, per + n, [](int i, int j){  return st[i] < st[j];  });    int p = -1;    for_each(per, per + n, [&p](int &i){            while(p != -1 && en[p] < en[i])                p = ans[p];            ans[i] = p;            p = i;        });    for(int i = 0; i < n; i++)        cout << ans[i] + 1 << ' ';    cout << '\n';}`