L22. Top View of Binary Tree | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@virajdhumal1621]

Sure!

[@InBracket]

🤟❤️

[@jitishgupta6424]

why ?

[@homiraghuvanshi3436]

Hey, when can we find the complete tree series available on this playlist(As the intern season is very very near and your videos are just superb)? What are the benefits of joining your channel?

[@homiraghuvanshi3436]

Can you suggest an alternate resource that can cover the type of questions that are left to be uploaded by you?

[@bhargavnagacharan1899]

Bro thanks alot 🥺🥺🙏🙏🙏. All KZbin channels are making videos in hindi. I can't understand hindi, you are the one among very few KZbinrs who provide best content in English and also u r the only one who gives both c++ and java code 🥺🥺❤️ love uuuuu💯💯💯💯.

[@uRamPlus]

indeed! appreciate he explains in English! this channel is a hidden gem 💎

[@anonymous-sk2pr]

@@its_me_hb 😂😂😂 nice joke idont know hindi but I live in India and I don't need your permission for that😎😎😎

[@anonymous-sk2pr]

@@its_me_hb bring your mom along with you I'll dance with her infront of you😎😎😎

[@its_me_hb]

Lol

[@achinttrivedi4667]

i better like hindi channels, after watching your i recognize that this person was speaking in english. Hahaha this guy makes everything easy without any language barrier

[@ElderMoro]

Times Complexity should be O(NlogN) because we're using map in CPP which takes logN time to insert in the map and there are N nodes so TC will be O(NlogN).

[@mysteryman2213]

in java it takes O(1) average

[@naveen9646]

also to check if a element is present it takes O(logN) Note: this is for ordered_map. If it is a unordered map it would be O(1) except for worst case O(N)[rare case]

[@mohdtalha433]

@@mysteryman2213 jalva hai JAVA walo ka

[@Kshitijsingh-n7f]

yes

[@ElderMoro]

@@Kshitijsingh-n7f well i prefer cpp

[@_PRANAYMATE]

Hey Striver , I have written down the code on my own for this problem after understanding the solution, I know it's the cake work but it gives much satisfaction that understand the logic and prepare the code than just watching the code and typing it Thanks a lot ❤❤❤❤

[@sparshsharma6068]

I literally saw 3-4 videos on this question but still was not able to get AC on GFG practice, in frustration, I left this question but now after watching your video, this question has become one of my favorite questions on trees. Thank you bhaiya!! EDIT: I cut down the time complexity of inserting elements in treemap(O(logN)) to O(1) by using a Hash Map. I just stored the min value of the line in the tree and then kept on incrementing from that and kept on storing the elements. JAVA Code: class Pair{ int state; Node root; Pair(int state, Node root){ this.state = state; this.root = root; } } class Solution { //Function to return a list of nodes visible from the top view //from left to right in Binary Tree. static int traverseLevelOrder(Node root, Map map){ Queue queue = new LinkedList(); queue.offer(new Pair(0,root)); int min = Integer.MAX_VALUE; while(!queue.isEmpty()){ Pair pair = queue.poll(); Node currNode = pair.root; int state = pair.state; min = Math.min(min, state); if(!map.containsKey(state)) map.put(state, currNode.data); if(currNode.left != null) queue.offer(new Pair(state-1, currNode.left)); if(currNode.right != null) queue.offer(new Pair(state+1, currNode.right)); } return min; } static ArrayList topView(Node root) { //This question can't be done using normal dfs beacuse there is a concept //of levels being used in this question Map map = new HashMap(); int min = traverseLevelOrder(root, map); ArrayList ans = new ArrayList(); for(int i = min; map.containsKey(i); i++) ans.add(map.get(i)); return ans; } }

[@takeUforward]

Amazing!

[@supratimbhattacharjee5324]

It also took me lot of time to solve recursively.....In the end after many failed attempts I solved this question on my own

[@sparshsharma6068]

@@supratimbhattacharjee5324 I can relate to you.

[@ghazanferwahab5673]

int state = pair.state; i could not understand this line plz explain

[@sparshsharma6068]

@@ghazanferwahab5673 We were pushing objects of Pair class(which had properties of: int state and Node root) in our queue. root is the reference to the node in the tree and state is basically the values written above the lines in the video at timestamp : 2:26 Pair pair = queue.poll(); //Here, we extract the object from the queue Node currNode = pair.root; //Then, from the object extracted above(named pair) we extract the node reference int state = pair.state; //And on this line, we extract the state I hope it helps!

[@Xp-Sam]

// NOTE: In dfs there is always a possibility that some bottom nodes are visited first before the top view nodes, so we have to keep track of the levels too void dfs(TreeNode* root, map &mp, int level, int column){ if(root){ if(mp.find(column) == mp.end() || mp[column].second > level)mp[column]= {root->val, level}; dfs(root->left, mp, level+1, column-1); dfs(root->right, mp, level+1, column+1); } } vector getTopView(TreeNode *root) { if(root == NULL )return {}; map mp; dfs(root, mp, 0, 0); vector ans; for(auto x : mp){ ans.push_back(x.second.first); } return ans; }

[@tanujsaini3993]

Great

[@prakhargupta5410]

very insightful was thinking the same thing

[@tanishq2766]

Yeah and in the vertical view we already do keep the two coordinates with us even in the queue solution.

[@abhinavsingh8246]

Will the case be same if we do preorder traversal ? as it visits the root first . In that case I don't think so there is a need for maintaining level?? where am I wrong ??

[@Xp-Sam]

@@abhinavsingh8246 write the code and you will get to know

[@ashwinnema06]

I solved this problem on gfg by watching this video for the first 3 minutes. Thank you for explaining question nicely

[@joshrak3412]

I just used the same concept of vertical order traversal and just added a break statement after inserting the first element of every vertical to make sure that I always get the top-most element of every vertical basically that's the top-view void traverse(TreeNode* node, map &ds, int vertical, int level){ if(node==NULL) return; ds[vertical][level].insert(node->val); traverse(node->left,ds,vertical-1,level+1); traverse(node->right,ds,vertical+1,level+1); } vector getTopView(TreeNode *root) { map ds; traverse(root,ds,0,0); vector ans; for(auto it:ds){ for(auto it1:it.second){ for(auto it2:it1.second){ ans.push_back(it2); break; } break; } } return ans; }

[@krishnakantupadhyay3053]

yeah I did the same but it's not working for few test cases don't know why

[@ishitg9937]

@@krishnakantupadhyay3053 keeping a multiset will sort the values, here we only need one who comes first, so use a vector instead

[@KatikaneniDharaniidhar]

we can also solve this using the boundary traversal approach since the only thing that is different is that here we are not printing the leaf nodes but we are traversingg through the left and right so this would take O(h+h) for both left and right

[@dakshsingh5891]

wont work because some nodes will be covered by the shadow of top nodes so only the most left or most right only at the top matter so it requires the use of x and y coordinates.

[@guptafactory]

O(N) T.C. C++ solution: Take 2 variables l and r and initialize it to 0,0 denoting leftmost col/line and rightmost col/line we already had. Take queue "que" for holding all Nodes with their line/col, a stack "left" (for leftmost nodes), a queue "right" (for rightmost nodes). Add root to the "left" and "que". Iterate level by level (BFS) and check: If current nodes col/line < l , update l and put node's value to "left" stack. If current nodes col/line > r, update r and put node's value to "right" queue. Now create a final ans vector/list. Push all elements from "left" stack to "ans". Then, Push all elements from "right" queue to "ans". And, Return ans. Code: class Solution { public: //Function to return a list of nodes visible from the top view //from left to right in Binary Tree. vector topView(Node *root) { vector ans; if (root == NULL) return ans; int l = 0, r = 0, col = 0; queue que; stack left; queue right; que.push({root, 0}); left.push(root->data); while (!que.empty()) { int sz = que.size(); while (sz--) { auto it = que.front(); que.pop(); Node* node = it.first; col = it.second; if (col < l) { left.push(node->data); l = col; } if (col > r) { right.push(node->data); r = col; } if (node->left) que.push({node->left, col - 1}); if (node->right) que.push({node->right, col + 1}); } } while (!left.empty()) { ans.push_back(left.top()); left.pop(); } while (!right.empty()) { ans.push_back(right.front()); right.pop(); } return ans; } };

[@manasambhat1328]

I usually never comment on the youtube videos. But this explanation was amazing. Reminds of the codeschool channel. Keep up the good work bro.

[@aadityavaid6818]

By using unordered_map we can take two more variables (mini and maxi) to keep account of lowest vertical and highest vertical and then iterate from mini to maxi

[@VishalGupta-xw2rp]

By Recursion Make 2 functions Call Left Function - Use Inorder Then save root node Call Right Function - Use Preorder #Striver_our_Saviour

[@symbol767]

Wow this is the same as vertical order traversal but just taking 1 node (the first node) So I am guessing bottom view is gonna be the same, except we take the last node on each vertical level

[@abhinabaprakashbora903]

I think we can do it recursively by using two functions : One for the left top view and the other for the right top view

[@gundalaavinash2438]

no bro it doesn't works , Please try to apply for this example 1 / \ 2 3 \ 4 \ 5 \ 6

[@abhinabaprakashbora903]

@@gundalaavinash2438 its working bro

[@abhinabaprakashbora903]

void topviewl(node *root, int countl, int &m, vector &res) { if (root == NULL) return; if (countl > m) { res.pb(root->data); m = countl; } topviewl(root->left, countl + 1, m, res); topviewl(root->right, countl - 1, m, res); } void topviewr(node *root, int countr, int &m, vector &res) { if (root == NULL) return; if (countr > m) { res.pb(root->data); m = countr; } topviewr(root->right, countr + 1, m, res); topviewr(root->left, countr - 1, m, res); } void topview(node *root) { int m = -1; vector res; topviewl(root, 0, m, res); reverse(res.begin(), res.end()); m = 0; topviewr(root, 0, m, res); for (auto itr : res) cout

[@thegreekgoat98]

@@abhinabaprakashbora903 no its not

[@wernerheisenberg9653]

It won't work for this test case: 1 2 10 N 3 11 N N 4 12 N 6 N 13 N 7 N 8 N 9

[@Usurperhk]

As video starts, back to back two ads popped up, Me : "Seh lenge thoda...." BW. Great content on tree. Ab toh interviewer se bhi jyada janta hu 😂😂😂😂

[@anishkarthik4309]

@takeUforward I think time Complexity id O(n * log n), since map is a sorted data structure it takes O(log n) for find and insertion.

[@anilsuthar7623]

Time complexity of insertion in Map is Log(N) so total time complexity will be O(N log(N)) ;

[@legendsoflife3955]

does anyone cares 🤣🤣

[@swarnimkamal2210]

@@legendsoflife3955 yes the company will care O(nlogn) will result in TLE error

[@pradhyumnsharma976]

@@swarnimkamal2210 We can implement using unordered_map which takes O(1)

[@himanshusoni1512]

@@pradhyumnsharma976 and then how would you print/output the view in right manner?

[@abhinavkohli4293]

yes but i think so too but why did striver said o(n)

[@codeaddict474]

bhaiya aap ka smjane ka trika alg level ka i loved it🙏🙏🙏

[@rawat_ji5183]

I was having doubt why not pre-order but at the end of video it was cleared perfectly ... thanks 😁😁 for perfect explanation

[@kailin8311]

simple answered, well explained

[@shreyxnsh.14]

quite similar as the previous one: class Solution { public: //Function to return a list of nodes visible from the top view //from left to right in Binary Tree. vector topView(Node *root) { //Your code here vector ans; if(root == NULL) return ans; queue q; map mpp; q.push({root, {0, 0}}); while(!q.empty()){ Node* node = q.front().first; int vert = q.front().second.first; int level = q.front().second.second; if(mpp[vert][level].size() == 0) mpp[vert][level].insert(node->data); q.pop(); if(node->left) q.push({node->left , {vert - 1, level + 1}}); if(node->right) q.push({node->right , {vert + 1, level + 1}}); } for(const auto& it: mpp){ vector temp; for(const auto &itt: it.second){ // temp.insert(temp.end(), itt.second.begin(), itt.second.end()); multiset ms = itt.second; for(const auto& ittt: ms){ temp.push_back(ittt); } } ans.push_back(temp[0]); } return ans; } };

[@shreyxnsh.14]

optimised version: vector ans; if(root == NULL) return ans; queue q; map mpp; q.push({root, 0}); while(!q.empty()){ Node* node = q.front().first; int vert = q.front().second; if(mpp.find(vert) == mpp.end()) mpp[vert] = node->data; q.pop(); if(node->left) q.push({node->left , vert - 1}); if(node->right) q.push({node->right , vert + 1}); } for(const auto& it: mpp){ ans.push_back(it.second); } return ans;

[@shaikfahim1232]

class Solution { public: //Function to return a list of nodes visible from the top view //from left to right in Binary Tree. vector topView(Node *root) { //Your code here vector ans,revans; if(!root) return ans; map umap; int vertical=0; umap.insert({vertical,root->data}); funleft(root->left,umap,vertical-1); funright(root->right,umap,vertical+1); for(auto x:umap) { ans.push_back(x.second); } return ans; } void funleft(Node *root,map &umap,int vertical) { if(!root) return; if(umap.find(vertical)==umap.end()); umap.insert({vertical,root->data}); if((root->left)) funleft(root->left,umap,vertical-1); else funleft(root->right,umap,vertical+1); } void funright(Node *root,map &umap,int vertical) { if(!root) return; if(umap.find(vertical)==umap.end()); umap.insert({vertical,root->data}); if((root->right)) funright(root->right,umap,vertical+1); else funright(root->left,umap,vertical-1); } }; everything's right here but iam getting error for just the rightmost node

[@stith_pragya]

Thanks for this wonderful video....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@harshbhagwani7769]

RECURSIVE PYTHON SOLN FOR TOP VIEW OF BINARY TREE : class Solution: def __init__(self): self.values={} def solve(self,root,x,level): if root is None : return if x not in self.values.keys() or self.values[x][1]>level: self.values[x]=[root.data,level] self.solve(root.left,x-1,level+1) self.solve(root.right,x+1,level+1) def topView(self,root): self.solve(root,0,0) result=[] for i in sorted(self.values.keys()): result.append(self.values[i][0]) return result

[@ajaykushwaha6137]

Hey I liked your approach, but I think we can do it recursively as well. Since we are always inserting the first element from Vertical Order Traversal array, which could also be done using pre-order Traversaln in recursion. And we store ma (displacement, root->val) m and then check, if there will exist a value for a particular displacement, insert the pair else do nothing and continue with traversal. Please look into this logic.

[@bharathkumar5870]

void fr(Node * root,int col,map &mp){ if(root==0) return; if(mp[col]==0){ mp[col]=root->data; } fr(root->left,col-1,mp); fr(root->right,col+1,mp); }

[@bharathkumar5870]

preorder doesnt work,some nodes which are under the top view are visited first

[@bharathkumar5870]

and also u can not solve with any other dfs method..For every dfs we can draw a tree such that bottom nodes are visited first before top view nodes.

[@your_name96]

@@bharathkumar5870 chill we just need to store the level as well to keep track of the topmost nodes of a horizontal distance column(video toh dekh le pura): void helper(Node* node,int l,int w,map&mp){ if(!node)return; if(!mp.count(w) or l < mp[w].first){ mp[w] = {l,node->data}; } helper(node->left,l+1,w-1,mp); helper(node->right,l+1,w+1,mp); } vector topView(Node *root) { //Your code here if(!root)return {}; vectorres; mapmp; helper(root,0,0,mp); for(auto &el : mp){ res.push_back(el.second.second); } return res; }

[@bharathkumar5870]

@@your_name96 thanks..I waited for 8 months for this solution..you saved my life..ur the best coder I have ever seen

[@jitinroy2246]

In TUF WEBSITE article of java code these lines missing, please edit the article. class Pair{ Node node; int vertical; public Pair(Node n, int v){ node=n; vertical=v; } }

[@Ramu9119]

Man you are awesome this and vertical order traversal is exactly similar to each other there we keep a multiset or vector as necessary here we only store a element which comes first

[@lifehustlers164]

Completed 23/54 (42% done) !!!

[@mdaman6448]

Thanks for the free ka tree series :) great content... Bhaiya..

[@lone_wolf7721]

Other people :- binge watch netflix me:- binge watch free ka tree series

[@syedhabeebuddin101]

I left this question after watching the improper explanations of other youtubers. when i came to know that you uploaded the Tree series i just checked out the variety of questions you covered in it Because I know, somehow i m gonna get all of them.

[@bsaikumarreddy1413]

Iterate over map. Map treeMap = new TreeMap(); ArrayList topView = new ArrayList(); for (Integer value : treeMap.values()) { topView.add(value); } // topView.addAll(treeMap.values());

[@ashwinbalaji26]

Instead of mpp.find() and then mpp[line] = node->data we can use mpp.insert({line,node->data}) because the insert func inserts the key value pair only if key is not present already. This is for c++, I am not sure about java or python 8:01

[@mohammadnajmuddin7511]

thanks alot bro for making tree series

[@shivambajpeyi9008]

Understooooood! Surprised to see I code exactly like u, even I didn't see the video Haha!

[@gamerversez5372]

Recursive Code in C++ if anybody wants :) void solve(Node* root, int col, int row, map& x) { if (root == nullptr) { return; } x[col][row].push_back(root->data); solve(root->left, col - 1, row + 1, x); solve(root->right, col + 1, row + 1, x); } vector topView(Node *root) { map x; solve(root, 0, 0, x); vector ans; for (auto col : x) { for (auto row : col.second) { int val = row.second[0]; ans.push_back(val); break; } } return ans; }

[@VV-ps8rt]

Python Version dfs and bfs: # # Recursive Approach: # use dfs traversal and use a col and level variables that we used in vertical traversal # but here we just need to print the outermost ie top level nodes from each col so store those col and level in mapp # now traverse and check if that col in mapp and if its present from its values ie [level, root] check # if level in mapp is greater than current level if its not then update col with current level and root # here as we move downwards in the tree we will reduce level so it becomes easier to compare to get top level # and at the end sort the mapp keys and return values def TopViewQ(root): def topview(root,col,level): if not root: return if col in mapp: if level>mapp[col][0]: mapp[col]=[level,root.value] else: mapp[col]=[level,root.value] topview(root.left,col-1,level-1) topview(root.right,col+1,level-1) from collections import defaultdict mapp=defaultdict(list) topview(root,0,0) # print(mapp) return [mapp[x][1] for x in sorted(mapp)] # # ///////////////////////////////////////////////////////////// # Iterative Appraoch: # similar to dfs we just replace it with bfs def TopViewQ(root): import collections mapp=collections.defaultdict(list) q=collections.deque([[root,0,0]]) while q: for i in range(len(q)): temp,col,level=q.popleft() if temp.left: q.append([temp.left,col-1,level-1]) if temp.right: q.append([temp.right,col+1,level-1]) if col in mapp: if level>mapp[col][0]: mapp[col]=[level,temp.value] else: mapp[col]=[level,temp.value] # print(mapp) return [mapp[x][1] for x in sorted(mapp)]

[@akarshitgupta6359]

Understood! So wonderful explanation as always, i have written code using unordered_map vector topView(Node *root) { vector res; if (!root) return res; unordered_map hash; int mini = 0; queue q; q.push({root,0}); while(!q.empty()){ auto temp = q.front(); q.pop(); Node* top = temp.first; int index = temp.second; mini = min(index,mini); if(hash.find(index)==hash.end()){hash[index] = top->data;} if(top->left) q.push({top->left,index-1}); if(top->right) q.push({top->right,index+1}); } while(hash.find(mini)!=hash.end()){res.push_back(hash[mini++]);} return res; }

[@Negijicoder]

really i just watch 2 min video and able to do it.. first i''m trying only the dfs(preorder) then i realize it's wrong.. then after watching the 2 min video where you said only bfs (level order) then i realise it.. and able to do it by myself thx a lot..

[@munikiranch726]

why dfs does not work?

[@Negijicoder]

@@munikiranch726 bro video me btaya hai bhaiya ne

[@DeadPoolx1712]

UNDERSTOOD;

[@letsrock7354]

bhaisaahab maza aa gaya...I used to think this vertical order traversal and all is so hard....but now it feels like a cakewalk I can get AC on leetcode even when I m sleepcoding

[@thatowlfromhogwarts490]

thanks alot striver bhaiya!!!!

[@ishangujarathi10]

love the intuition and approach!!! understood!!

[@aanchalmittal9897]

Understood!!....But can we directly tell this answer or do we need to tell other approaches as well?

[@aryanyadav3926]

Thank you very much sir for this video. I have a doubt, shouldn't the time complexity be O(nlogn) as we are using an ordered map which takes O(logn) to insert one element.

[@VeenaKumari-wn7us]

We can use list stl list l; .... if(line > l.back.first) l.push_back(line,node) if(line < l.front.first) l.push_front(line,node)

[@SHASHANKRUSTAGII]

it is nlog^3n

[@abhinavkohli4293]

I have the same doubt how it is O(n) on some time complexity calculator also it is saying O(n) but it should be O(nlogn) pls tell me if you know how

[@apmotivationakashparmar722]

Thank you so much

[@keshavbiyani9202]

I think we can improve the time complexity by taking an unordered map and keeping a track of minimum x and maximum x as and when we pop an item from the Q. Then eventually doing a for loop from minimum x to maximum x somewhat like this in Python. In case I am missing something, please let me know. Thanks. from collections import deque class Solution: #Function to return a list of nodes visible from the top view #from left to right in Binary Tree. def topView(self,root): # code here if not root: return [] q = deque() data = {} q.append((root, 0)) xmin, xmax = 0,0 while q: node, x = q.popleft() if x not in data: data[x] = node.data if node.left: q.append((node.left, x-1)) xmin = min(xmin, x-1) if node.right: q.append((node.right, x+1)) xmax = max(xmax, x+1) result = [] # print(data) for i in range(xmin, xmax+1): result.append(data[i]) return result

[@mangeshthakare9485]

For showing top view of binary tree , Why can't we just go extreme left put them in stack pop them and store them in list. Then go extreme right and store them in list. This is more easier. It also has same TC O(N)

[@gangsta_coder_12]

Excellent explanation as always. 👌👌🔥🔥🔥

[@anutoshghosh7893]

Thanks a lot for teaching such quality content, hats off to Striver, the Pair class also needs to be defined in java code? How to arrange and sort the answer from left to right?

[@MohitSharma-tt3uk]

Please please please 🙏🙏🙏 Dynamic Programming and Graph Questions just like this playlist.

[@shreyxnsh.14]

Optmised version: vector ans; if(root == NULL) return ans; queue q; map mpp; q.push({root, 0}); while(!q.empty()){ Node* node = q.front().first; int vert = q.front().second; if(mpp.find(vert) == mpp.end()) mpp[vert] = node->data; q.pop(); if(node->left) q.push({node->left , vert - 1}); if(node->right) q.push({node->right , vert + 1}); } for(const auto& it: mpp){ ans.push_back(it.second); } return ans;

[@PalakMittal]

Amazing Explanation bhaiya !

[@SibiRanganathL]

Understood

[@cinime]

Understood! So wonderful explanation as always, thank you very much!!

[@uRamPlus]

Thank you for your hard work and effort! 💎

[@KartikeyTT]

tysm sir

[@tps8470]

Thanks

[@adebisisheriff159]

Thanks Striver!!!

[@SHASHANKRUSTAGII]

This question, and the previous question, both can be solved without queue, we can use a vector!!!

[@akashverma5756]

This problem is deceptively hard.

[@MohanaKrishnaVH]

Awesome Explanation! Understood.

[@anumoynandy5811]

Correct me if I am wrong , over here you used a map , and basic functionality of it is just maintain the order of the keys , in O(logN) time , and in worst case , we gonna explore all the N nodes , isn't the time complexity == O(N*logN) ???

[@takeUforward]

Yes but unordered maps take o(1), in java also, you can assume the complexity and multiply with N. as long as you understand, it works 😇

[@chandrachurmukherjeejucse5816]

Understood. C++ code with dfs: void inorder(TreeNode* root, int x, int y, map &topView) { if(root == NULL) return; if(topView.find(x) == topView.end() || y < topView[x].first) { topView[x].first = y; topView[x].second = root -> val; } inorder(root -> left, x - 1, y + 1, topView); inorder(root -> right, x + 1, y + 1, topView); } vector getTopView(TreeNode *root) { vector res; if(root == NULL) return res; // x y val map topView; inorder(root, 0, 0, topView); for(auto p: topView) { res.push_back(p.second.second); } return res; }

[@bhagyashreekhairnar683]

Thank you

[@kewtomrao]

That eye there reminds me of my jee days :)

[@parthsalat]

Understood kaka!

[@chiranmoybhattacharya5923]

This is O(nlogn) solution, just imagine a skewed tree where every node has to be put into the map and every insertion in ordered map costs O(logn). For O(n) use a linkedlist and left, right integers to represent the boundaries. If the horizontal distance of a node is less than left, add to the front of the list. If the horizontal distance of a node is more than right, add at the end. Here's the code class Solution { static ArrayList topView(Node root) { int left = 0, right = -1; Deque queue = new LinkedList(); LinkedList list = new LinkedList(); queue.addLast(new Pair(root, 0)); while (!queue.isEmpty()) { Pair node = queue.removeFirst(); if (node.position < left) { list.addFirst(node.root.data); left--; } if (node.position > right) { list.addLast(node.root.data); right++; } if (node.root.left != null) queue.addLast(new Pair(node.root.left, node.position - 1)); if (node.root.right != null) queue.addLast(new Pair(node.root.right, node.position + 1)); } return new ArrayList(list); } private static class Pair { final Node root; final int position; public Pair(Node root, int position) { this.root = root; this.position = position; } } }

[@rohit2571]

you can also use a unordered map in C++ and keep two variables minHorizontalDistance and maxHorizontalDistance to traverse the map

[@arnab4151]

In case anyone needs help: // Problem link: practice.geeksforgeeks.org/problems/top-view-of-binary-tree/1 // Approach 1: Recursive Approach: class Solution{ public: void topViewUtil(Node *root, int distance, int height, map &mp){ if(root == NULL) return; if(mp.find(distance) == mp.end()) mp[distance] = {height, root->data}; else{ if(mp[distance].first >= height) mp[distance] = {height, root->data}; } topViewUtil(root->left, distance - 1, height + 1, mp); topViewUtil(root->right, distance + 1, height + 1, mp); } vector topView(Node *root){ map mp; // {distance, {level, ans}} int distance = 0; // How farther away towards left/right from the root int height = 1; topViewUtil(root, distance, height, mp); vector ans; for(auto it : mp) ans.push_back(it.second.second); return ans; } }; // Approach 2: Iterative Approach: class Solution{ public: vector topView(Node *root){ if(root == NULL) return {}; map mp; // {distance, ans} queue q; // {node, distance} q.push({root, 0}); while(!q.empty()){ int sz = (int)q.size(); for(int i = 0; i < sz; i++){ auto cur = q.front(); q.pop(); if(mp.find(cur.second) == mp.end()) mp[cur.second] = cur.first->data; if(cur.first->left != NULL) q.push({cur.first->left, cur.second - 1}); if(cur.first->right != NULL) q.push({cur.first->right, cur.second + 1}); } } vector ans; for(auto it : mp) ans.push_back(it.second); return ans; } };

[@deepakantoj432]

can some explain why this wouldn't work i keep going left and add it to list and return then add the root and then i keep adding the node and moving right static ArrayList topView(Node root) { // add your code ArrayList list = new ArrayList(); rl(root.left , list); list.add(root.data); rr(root.right, list); return list; } public static void rl(Node root , ArrayList list) { if(root == null) return ; rl(root.left , list); list.add(root.data); } public static void rr(Node root , ArrayList list) { if(root == null) return ; list.add(root.data); rl(root.right, list); }

[@anshpradhan1954]

the eye tho 👌👍

[@ManojKumar-jb4sc]

In java solution i not understand the map creation syntax Map map = new TreeNode why `new TreeNode` is used here? also in Queue q = new LinkedList why 'new LinkedList' is used?

[@sahilzainuddin7134]

It's TreeMap and not TreeNode.

[@ManojKumar-jb4sc]

@@sahilzainuddin7134 still not get it😔

[@ritabratanag1821]

@@ManojKumar-jb4sc Map allows unique entries.. So a TreeMap is used

[@noobchess2516]

my code in which we consider both x and y coordinate but we pick x coordinate in ascending order which has minimum y coordinate . if you try to visualize the logic in a tree you will get better understanding but it cannot pass 1 testcase can someone find the issue it would be helpful i am stuck and dont want to cram the solution .code--> struct point{ int value; int x; int y; }; void travel(TreeNode*root,vector&a,int x,int y){ if(root==NULL){ return; } point store; store.value = root->data; store.x= x; store.y=y; a.push_back(store); travel(root->left,a,x-1,y+1); travel(root->right,a,x+1,y+1); } bool compare(point a,point b){ if(a.x!=b.x){ return a.x

[@codetochange8]

Thanks Striver...as always ❤

[@mriduljain1981]

completed lecture 22 of free ka tree series.

[@pritishpattnaik4674]

Great Explanation Striver bhaiya

[@harshitjaiswal9439]

understood

[@stark2461]

Time complexity of this code will be O(NlogN) but for this problem still we cut it down to O(N)

[@UECAshutoshKumar]

Thank you sir

[@alesblaze4745]

Thanks mate!

[@its_me136]

recursive solution:- mapmp; vectortemp; void solve(Node*root,int row,int col) { if(!root) return; if(mp.find(col)==mp.end()||mp[col].second>row) mp[col]={root->data,row}; solve(root->left,row+1,col-1); solve(root->right,row+1,col+1); } vectorverticalTraversal(Node* root) { if(!root) return {}; solve(root,0,0); for(auto it:mp) { temp.push_back(it.second.first); } return temp; } vector topView(Node *root) { if(!root) return {}; return verticalTraversal(root); } };

[@MdAsif-eo9lm]

plz assign each variable with proper name.. it helps to understand the code

[@utkarshsharma6650]

understooood. thanks :) would revise soon

[@debdhritiroy6868]

I think in this case a deque serves the best to get O(N) T.C. , otherwise inserting into the map will cost O(logN)

[@alokamgnaneswarasai5158]

Then you have to spare time for sorting at last

[@debdhritiroy6868]

@@alokamgnaneswarasai5158 well i think, No it doesn't need that, we just insert the node of the newfound width to front or back, and maintain 2 pointers marking the new needed width on both sides😶

[@abhaykumarsingh3884]

recursive soln for above question using concept of vertical traversal static class Pair{ int x; int y; Pair(int x,int y){ this.x=x; this.y=y; } } public static void getAns(TreeNode root,TreeMap map,int row,int col){ if(root==null){ return; } if(!map.containsKey(row)){ map.put(row,new Pair(col, root.val)); } else{ Pair p=map.get(row); if(p.x > col){ p.x=col; p.y=root.val; map.put(row,p); } } getAns(root.left,map,row-1,col+1); getAns(root.right,map,row+1,col+1); } public static ArrayList getTopView(TreeNode root) { TreeMap map=new TreeMap(); ArrayList ans=new ArrayList(); getAns(root,map,0,0); for(Map.Entry entry:map.entrySet()){ ans.add(entry.getValue().y); } return ans; }

[@AyushGupta-ux4gq]

class Solution { public: vector verticalTraversal(Node* root) { // return {}; if (root == NULL) { return {}; } map mpp; queue q; // node,vertical,level q.push({root, 0}); while (!q.empty()) { int m = q.size(); for (int i = 0; i < m; i++) { Node* curr = q.front().first; int v = q.front().second; if(mpp.find(v)==mpp.end()) { mpp[v]=curr->data; } q.pop(); if (curr->left != NULL) { q.push({curr->left,v - 1}); } if (curr->right != NULL) { q.push({curr->right, v + 1}); } } } vector ans; for (auto it : mpp) { ans.push_back(it.second); } return ans; } vector topView(Node *root) { //Your code here return verticalTraversal(root); }

[@joelsiby]

Great explanation

[@zangruver132]

but isnt using Map in C++ making it NlogN?

[@PrinceKumar-el7ob]

yeah but we needed it to be sorted as required per question so hence anyway we have to sort it that's why we are using map instead of unordered_map.

[@naveen9646]

This code can be used even for recursive method vector topView(Node *root) { //Your code here int maxleft=0,maxright=0; vector ans; set s; if(root==NULL) return ans; queue q; q.push({0,root}); s.insert({0,root->data}); while(!q.empty()){ int i=q.size(); while(i--){ auto p=q.front(); q.pop(); auto x=p.first; auto y=p.second; if(xdata}); maxleft=x;} if(x>maxright){s.insert({x,y->data});maxright=x;} if(y->left) q.push({x-1,y->left}); if(y->right) q.push({x+1,y->right}); } } for(auto i:s) ans.push_back(i.second); return ans; }

[@kushgupta1673]

cant we use boundary traversal from left corner to right corner without taking all leaver?

[@pervejmia8240]

Recursion Solution : www.techiedelight.com/print-top-view-binary-tree/

[@ganavin3423]

understood bhaiya

[@supratimbhattacharjee5324]

//Both recursive and iterative solutions class Solution { public: //Function to return a list of nodes visible from the top view //from left to right in Binary Tree. void traverse(Node* root,int spreadLevel,int verticalLevel,map& spread) { if(root==nullptr) return; if(spread.find(spreadLevel)==spread.end()) spread.insert({spreadLevel,{verticalLevel,root->data}}); else { if(verticalLeveldata; spread[spreadLevel].first=verticalLevel; } } traverse(root->left,spreadLevel-1,verticalLevel+1,spread); traverse(root->right,spreadLevel+1,verticalLevel+1,spread); } vector topView(Node *root) { vector ans; if(root==nullptr) return ans; //horizontal level, vertical level, value map spread; int spreadLevel=0; int verticalLevel=0; traverse(root,spreadLevel,verticalLevel,spread); for(auto x: spread) ans.push_back(x.second.second); return ans; } }; class Solution { public: //Function to return a list of nodes visible from the top view //from left to right in Binary Tree. vector topView(Node *root) { vector ans; map levelNode; if(!root) return ans; queue q; q.push({root,0}); while(!q.empty()) { pair curNode=q.front(); levelNode.insert({curNode.second,curNode.first->data}); q.pop(); if(curNode.first->left) q.push({curNode.first->left,curNode.second-1}); if(curNode.first->right) q.push({curNode.first->right,curNode.second+1}); } for(auto it=levelNode.begin();it!=levelNode.end();it++) ans.push_back(it->second); return ans; } };

[@nagavedareddy5891]

Huge respect...❤👏

[@manthanpatil2268]

Great approach bhai

[@lavanyaprakashjampana933]

we love your content and we love you...🖤

[@anonymous090]

Thank you 😊

[@siddhanttyagi6653]

bhaiya .thank you for such great content

[@uvs_6032]

*INORDER CODE* class Solution { public: void inOrder(TreeNode* node,int x,int y,map& ds) { if(node==nullptr) return; inOrder(node->left,x-1,y+1,ds); ds[x][y].insert(node->val); inOrder(node->right,x+1,y+1,ds); return; } vector verticalTraversal(TreeNode* root) { vector ans; if(root == nullptr) return ans; // vert lvl { set of nodes of that x and y } // x -- y -----> { } mapds; inOrder(root,0,0,ds); for(auto vert :ds) { vector column; for(auto lvl : vert.second) { column.insert(column.end(),lvl.second.begin(),lvl.second.end()); } ans.push_back(column); } return ans; } };

[@shivamehta6537]

Understood 😃

[@piyushacharya7696]

reach++ // JAVA class TreeNode { TreeNode left; TreeNode right; int val; TreeNode(int val) {this.val = val;}; TreeNode() {;} TreeNode(int val, TreeNode left,TreeNode right) { this.val = val; this.left = left; this.right = right; } } class Pair { int vertical; TreeNode node; public Pair(int vertical, TreeNode node) { this.vertical = vertical; this.node = node; } } public class TopViewBT { // the boundary traversal method wont work in this qn. take this testcase: /* 1 / \ 2 3 \ 4 \ 5 \ 6 Top view of the above binary tree is 2 1 3 6 */ static ArrayList topView(TreeNode root) { // add your code ArrayList ans = new ArrayList(); TreeMap map = new TreeMap(); if (root == null) return ans; Queue q = new LinkedList(); q.add(new Pair(0, root)); while (!q.isEmpty()) { Pair temp = q.poll(); int vertical = temp.vertical; TreeNode node = temp.node; // we will add the very first node of each vertical line. if (!map.containsKey(vertical)) { map.put(vertical, node.val); } if (node.left != null) { q.add(new Pair(vertical - 1, node.left)); } if (node.right != null) { q.add(new Pair(vertical + 1, node.right)); } } for (int nodes : map.values()) { ans.add(nodes); } return ans; } }