HackerEarth Restoring trees problem solution

YASH PAL, 31 July 202416 February 2026

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

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';
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply