You are not logged in. Please login at www.codechef.com to post your questions!

×

CDVA1602 - Editorial

PROBLEM LINK:

Practice
Contest

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<int> >. 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<int> >. 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<int> >) 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.

This question is marked "community wiki".

asked 30 Mar '16, 00:40

adi28galaxyak's gravatar image

5★adi28galaxyak
1164
accept rate: 14%

edited 30 Mar '16, 14:48

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×734
×711
×34
×4

question asked: 30 Mar '16, 00:40

question was seen: 878 times

last updated: 15 Dec '17, 01:01