PROBLEM LINK:
Author: Ashutosh Kumar
Tester: Suraj Prakash
Editorialist: Aditya Kumar
DIFFICULTY:
EASY
PREREQUISITES:
Tree, DFS or Similar
PROBLEM:
Given a binary tree. Anshu started climbing from the left. He was initially at the L^{th} level of the tree. Once he reaches the root of the tree, he slided down from the right side. Every level he sees a node. Your task to print these visited nodes in (non repeating) ascending orders.
QUICK EXPLANATION:
Apply depth first search from the root twice, once for the left side and second time for the right side. Initialize maximum height(mh) with 0 before each search.
Left dfs: Create a tree of vector< vector >. Whenever a node is visited for the first time, if its height (or the level where it is present) is greater than mh; update mh and add this node to answer set.
Right dfs: Just create a graph of vector< stack >. Apply the same logic of Left dfs.
EXPLANATION:
Let’s divide this problem into three parts; first when Anshu climbs the tree (from LEFT), second when he slides down the tree (from RIGHT), and finally third one - calculating answer set.
Clearly our answer set must contain all the nodes which lie at the extreme ends of each level in the tree. So to get these we need to traverse the tree and hence we can use depht first search or similar searches.
First part: Create the tree using adjacency list and initialize maximum height(mh) with 0. Now apply dfs at root node. Whenever a node is visited for the first time, if its height (or the level where it is present) is greater than mh; update mh and add this node to answer set.
vector<int> tree[MAX+5];
int mh = 0;
void ldfs(int id, int ht, int p = -1){
if(ht>mh) {
ans.insert(id);
mh = ht;
}
for(auto it: tree[id]){
if(it!=p){
ldfs(it, ht+1, id);
}
}
}
Second part: Create the tree using adjacency list (vector< stack >) do apply the same what we did in the first part. We have created a list of stack because we need the first node from right side at each level, which is nothing but the last node from left side.
mh = 0;
vector< stack<int> > rtree(MAX+5);
void rdfs(int id, int ht, int p=-1){
if(ht>mh) {
ans.insert(id);
mh = ht;
}
while(!rtree[id].empty()){
int x = rtree[id].top();
rtree[id].pop();
if(x!=p){
rdfs(x, ht+1, id);
}
}
}
Third part: We need a data structure for answer set. Our answer set needs to store non repeated nodes in non descending order, which can be implemented using Set. So, we are with our question, we just need to iterate over the set and print the elements.
OPTIMAL COMPLEXITY:
\mathcal{O}(N + \log K) where K is the number of levels.
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.
Editorialist’s solution can be found here.