Nice solution. But i found out a little bit optimization for the above solution. Consider d= horizontal diameter of the tree. Building Treemap takes o(dlogd). Instead of TreeMap use HashMap and maintain two static variables i.e., min and max and update the min and max values as min=Math.min(min,temp.hd); max=Math.max(max,temp.hd); for every iteration. Now traverse the HM from min to max and add those values to a new ArrayList. This will reduce the time complexity from O(n+dlogd) to O(n)
for implementing the queue method we can define three variables in class third one to store level and in the if condition we will check using or operator that if the level of incoming node is lesser than the already existing node it will replace the node. Please tell me if something is wrong with this approach . Open to other suggestions.
Few days ago, bhaiya you suggested a youtube channel for learning java from scratch (u told, u also learnt from there) please give that channel link again, I forget that channel name. 🙏🏻
Not sure if it is the correct logic for bottom view. Consider this example. 7(0) / \ 6 (-1) 2 (1) / \ / \ 5 ( -2 ) 1(0) 8(0) 2 (2) We have 2 0s at bottom, but the map would hold just 1 zero. So your logic would give -> 5, 8, 2 instead of 5,1,8,2. Or am I missing something?
Sir background video recorder app se user Jo video record karta hai kya vo video app Wale ke pass bhi store hota hai kya Kya ye possible hai ki Jo video hum record karte hain vo app Wale ke pass bhi store hota hai kya
You'll learn almost anything there's to learn about Data Structures & Algorithms so that you can crack Top companies technical interviews easily. Many of you have already done it. Best of Luck 🤗
static ArrayList topView(Node root) { Map map = new TreeMap(); int i=0; util(root,i,map); ArrayList ans = new ArrayList(); for(Map.Entry m : map.entrySet()){ int x = m.getValue(); ans.add(x); } public static void util(Node root, int i, Map map){ if(root==null) return; if(!map.containsKey(i)){ map.put(i,root.data); } util(root.left,i-1,map); util(root.right,i+1,map); } isme kya galti hai anyone ?
ans.add(x); } } you need to close extra } , :P Otherwise check the video again on 04:05, where Anuj Bhaiya explains why normal traversal (preorder) will fail
Can someone help me. What if we solve it in this way using DFS? class Solution { static int min=0, max=0; static ArrayList topView(Node root) { ArrayList res=new ArrayList(); Map mp=new HashMap(); helper(root, mp, 0, 0); for(int i=min;i vd) { mp.put(hd, new Pair(root.data, vd)); } } else { mp.put(hd, new Pair(root.data, vd)); } helper(root.left, mp, hd-1, vd+1); helper(root.right, mp, hd+1, vd+1); } } class Pair { int val, vd;// vd represents vertical distance from root AKA depth. public Pair(int a, int b) { val=a; vd=b; } }
Now I can say my Nonlinear Data structure journey has been started with Anuj Bhaiya 🙏🙏🙏🙏🙏 Thank You Sir ❣❣❣❣.
Nice solution.
But i found out a little bit optimization for the above solution.
Consider d= horizontal diameter of the tree.
Building Treemap takes o(dlogd).
Instead of TreeMap use HashMap and maintain two static variables i.e., min and max and update the min and max values as
min=Math.min(min,temp.hd);
max=Math.max(max,temp.hd);
for every iteration.
Now traverse the HM from min to max and add those values to a new ArrayList.
This will reduce the time complexity from O(n+dlogd) to O(n)
Bro please provide full solution
You're right i been thinking the same bro , use min max and hashmap
bro this is correct?
void topView(Node *root, int x, map &m)
{
if (root == NULL)
return;
if (m.find(x) == m.end())
{
m.insert(make_pair(x, root->data));
}
topView(root->left, x - 1, m);
topView(root->right, x + 1, m);
}
Nice one!
Never knew that this medium level topic is going to be so easy for me
Thank yoy
You are Such as Good Mentor 🥰 i really inspired your video when did I watch ❤
, vertical order, top view, bottom view, what an explanation ☺☺☺
Very Clean and Neat Explaination,Sir!
Thank you bhaiya , best explanation ever.
awesome bhaiya, thanks for making coding easier
You are genious dude…!!! Applauses 👌👌👌
So easily explained 😍. Thanku.
Great explaination
amazing with most difficult topic
Can you please provide a 60roamdap of important topics for DSA beginner to crack tech giant's like Microsoft linkedin etc
This is next in line.. will be coming out soon 😄 stay tuned
Thanks Sir !
Thank you so much bhaiya mai yhi same glti kar rha tha.... thank you
for implementing the queue method we can define three variables in class third one to store level and in the if condition we will check using or operator that if the level of incoming node is lesser than the already existing node it will replace the node. Please tell me if something is wrong with this approach . Open to other suggestions.
Thank you bhaiya
Thanks Anuj! Great job bro! 👌
Good Solution!
Nice explanation bhaiya
Few days ago, bhaiya you suggested a youtube channel for learning java from scratch (u told, u also learnt from there) please give that channel link again, I forget that channel name. 🙏🏻
Malum pada bhai
@@King-xs4tq ni bhai, agr pta chale to btana
@@anuj_abh Nahi bhai maine to bhaiya ke course se hi pada tha java lekin beginners ke liye utna fayde ka nahi h. Agar aapko malum padey to bataiyega
Thanks bhya . I am following you
Thank You Bhaiya🙏👌
Maaza aa gaya 😁
This video was helpful!
wonderful
Bhaiyaa DevOps par ek video banaiye isme career kaise banaye
loveddddd it
Not sure if it is the correct logic for bottom view.
Consider this example.
7(0)
/ \
6 (-1) 2 (1)
/ \ / \
5 ( -2 ) 1(0) 8(0) 2 (2)
We have 2 0s at bottom, but the map would hold just 1 zero. So your logic would give -> 5, 8, 2 instead of 5,1,8,2.
Or am I missing something?
See the video at 1:07. He talks about when two elements with same distance are met, we pick the right side one. Hence, 8 is picked up!
Output will like -> 5, 6, 8, 2, 2
❤❤❤
what is the time complexity of this solution
Largest BST
Sir background video recorder app se user Jo video record karta hai kya vo video app Wale ke pass bhi store hota hai kya
Kya ye possible hai ki Jo video hum record karte hain vo app Wale ke pass bhi store hota hai kya
did u have a computer science degree??
Bhaiya, TreeMap nahi use karke, Map ko sort kardein end me to kaam nahi banega ? :( (Not sure how to implement Treemap in javascript)
Ho jaega usse bhi
Is dsa course me kya sikhne ko milega
You'll learn almost anything there's to learn about Data Structures & Algorithms so that you can crack Top companies technical interviews easily. Many of you have already done it. Best of Luck 🤗
22nd link
many teachers can't even accept their mistakes
❤️❤️
why we don't take preorder traversal for bottom view , kindly give a tree example where preorder traversal gives wrong answer.
can somebody tell me why are we using level order only?
time complexity?
O(no. of nodes i guess)
static ArrayList topView(Node root)
{
Map map = new TreeMap();
int i=0;
util(root,i,map);
ArrayList ans = new ArrayList();
for(Map.Entry m : map.entrySet()){
int x = m.getValue();
ans.add(x);
}
public static void util(Node root, int i, Map map){
if(root==null)
return;
if(!map.containsKey(i)){
map.put(i,root.data);
}
util(root.left,i-1,map);
util(root.right,i+1,map);
}
isme kya galti hai anyone ?
ans.add(x);
}
}
you need to close extra } , :P
Otherwise check the video again on 04:05, where Anuj Bhaiya explains why normal traversal (preorder) will fail
@@pratikvishwakarma1599 bhai wo to thek h pr sare test cases pass nhi ho rhe
Binary code kya hota hai
Kya isse me kya kr sakta hu
@Kumar Chitransh abe😂😂
@Kumar Chitransh 😂
Can someone help me. What if we solve it in this way using DFS?
class Solution
{
static int min=0, max=0;
static ArrayList topView(Node root)
{
ArrayList res=new ArrayList();
Map mp=new HashMap();
helper(root, mp, 0, 0);
for(int i=min;i vd)
{
mp.put(hd, new Pair(root.data, vd));
}
}
else
{
mp.put(hd, new Pair(root.data, vd));
}
helper(root.left, mp, hd-1, vd+1);
helper(root.right, mp, hd+1, vd+1);
}
}
class Pair
{
int val, vd;// vd represents vertical distance from root AKA depth.
public Pair(int a, int b)
{
val=a;
vd=b;
}
}
It will be complicated bro but it's your choice how you want to do 😊
Thanks bhiya
Thanks bhaiya