In case the question asks to store the left value instead of right when both nodes are at same place, just do the level order traversal from right to left.
Understood. Recursive code: Modification: keep track of ht along with line and check if there is a element present on the line or not. If not then insert that, otherwise check if ht is greater than or equal to the previous or not. We have to include == becasue we will always traverse the left part first and then second so if in the right subtree there is a node at the same level then that will be the rightest one. void inorder(BinaryTreeNode* root, int x, int y, map &bottomView) { if(root == NULL) return; if(bottomView.find(x) == bottomView.end() || y >= bottomView[x].first) { bottomView[x].first = y; bottomView[x].second = root -> data; } inorder(root -> left, x - 1, y + 1, bottomView); inorder(root -> right, x + 1, y + 1, bottomView); } vector bottomView(BinaryTreeNode * root){ vector res; if(root == NULL) return res; // x y data map bottomView; inorder(root, 0, 0, bottomView); for(auto p: bottomView) { res.push_back(p.second.second); } return res; }
the change we can do is ig...we can carry another parameter as depth...and we will create a map like map ...where the int inside the pair is the depth...so we only update the vertical if the current depth is greater than the stored depth....maybe this should work
In top view of the tree we check before adding to the map if there is an existing node from that particular line number , simply remove that checking condition that's all your code for bottom view is done :)
explained very well, sirf apke video se bfs theek se samaj paya. also had a doubt, why cant we use recursion(postorder traversal) with map? once we map for each horizontal distance, we can ignore other nodes, during traversal.
if we use unordered_map and keep track of leftmost element we can actually keep the complexity to minimum . map has push and find complexity of log(N).....even though we are not pushing each element but we are checking whether to push or not for each element .
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]
Recursive soln: [JAVA] class Pair { int level; int nodeVal; Pair (int level, int nodeVal) { this.level = level; this.nodeVal = nodeVal; } } public class Solution { public static List bottomView(TreeNode root) { // Write your code here. TreeMap map = new TreeMap(); travel(0, 0, root, map); List ans = new ArrayList(); for (Pair pair: map.values()) ans.add(pair.nodeVal); return ans; } static void travel(int x, int y, TreeNode cur, TreeMap map) { if (cur == null) return; if (!map.containsKey(x)) map.put(x, new Pair(y, cur.val)); else if(map.get(x).level
@@takeUforward But u have used treeMap which has time complexity of O(logn) in worst case while inserting elements so the time complexity will O(nlogn)
or we could just do top view but remove the if statement which checks if the line already is there in the map, as we are essentially trying to put the latest value for a particular vertical line
The solution may be incorrect for the following tree: root = Node(0) root.left = Node(1) root.right = Node(2) root.left.right = Node(3) root.right.left = Node(4) Actual output: 1 4 5 Expected Output: 1 3 4 5 Output is incorrect because the distance of {node, node.left.right, node.right.left} for any node is the same. So, both node.left.right and node.right.left should be added to the output, instead of just selecting node.right.left.
There is no node with value (5) inserted into the tree according to the tree provided, and according to the tree the output should be 1 4 2. Yes vertical of {root, root->left->right, root->right->left} is same, but the value of {root->right->left} would be selected as it hides the 2 nodes {root, root->left->right} above it. Hope it helps!
But hash maps in Java are not sorted they put the values in random in if we want to sort it we need to use a comparator and which will again add up time complexity
My dfs version : void hlp(Node*root,int hd,int lvl, map&mp){ if(!root)return ; if(!mp.count(hd) or lvl >= mp[hd].first){ // = is very important as it prints the later node if they have the same coordinated mp[hd] = {lvl,root->data}; } hlp(root->left,hd-1,lvl+1,mp); hlp(root->right,hd+1,lvl+1,mp); } vector bottomView(Node *root) { // Your Code Here if(!root)return {}; vectorans; mapmp; if(!root->left and !root->right)return {root->data}; hlp(root,0,0,mp); for(auto &el : mp){ ans.push_back(el.second.second); } return ans; } Time : O(nlogn) Space : O(n)
Instead of bfs, I try to implement using dfs but it gives me the wrong answer map m; void dfs(Node* root, int cnt) { if (root == NULL) return ; m[cnt] = root->data; dfs(root->left, cnt-1); dfs(root->right,cnt+1); } vector bottomView(Node *root) { m.clear(); dfs(root,0); vector v; for (auto x : m) v.push_back(x.second); return v; }
![[Live] : ONE 169 วันนี้!! "อนาโตลี vs อูมาร์"](http://i.ytimg.com/vi/IK3YZVWuFJg/mqdefault.jpg)
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
can you share the pdf of this slide
// code for recrsive approach,just keep track of row number.
//Structur of map: colum_no={data,rownumber}
//if row number is larger than previous stored data,then replace.
void f(BinaryTreeNode * root, int row,int col,map &mp){
if(root==0)return;
if(row>=mp[col].second)
mp[col]={root->data,row};
f(root->left,row+1,col-1,mp);
f(root->right,row+1,col+1,mp);
}
In case the question asks to store the left value instead of right when both nodes are at same place, just do the level order traversal from right to left.
Genius
I am very much happy and impressed by the fact at last you let us know why one shouldn't use recursion . Awesome explaination Must Say !!!
Oh lol, I saw your interview today.
@@soumyamondal Heyaa , small world :P
you are popular on linkedin right?
lol i did it with recursion. also top view . its not like that we cant do it ,
You also learn from striver DSA playlist?
Understood.
Recursive code:
Modification: keep track of ht along with line and check if there is a element present on the line or not. If not then insert that, otherwise check if ht is greater than or equal to the previous or not. We have to include == becasue we will always traverse the left part first and then second so if in the right subtree there is a node at the same level then that will be the rightest one.
void inorder(BinaryTreeNode* root, int x, int y, map &bottomView) {
if(root == NULL) return;
if(bottomView.find(x) == bottomView.end() ||
y >= bottomView[x].first) {
bottomView[x].first = y;
bottomView[x].second = root -> data;
}
inorder(root -> left, x - 1, y + 1, bottomView);
inorder(root -> right, x + 1, y + 1, bottomView);
}
vector bottomView(BinaryTreeNode * root){
vector res;
if(root == NULL) return res;
// x y data
map bottomView;
inorder(root, 0, 0, bottomView);
for(auto p: bottomView) {
res.push_back(p.second.second);
}
return res;
}
TC will be O(N) for BFS Traversal * O(LogN) as we are using Map.
So overall O(N*LogN)
Yeah for space complexity you can say overall it will be O(N)
Yeas
can you please tell how T(c) will be O(N log n) , because in video he has mentioned T(c) to be O(N) .
@@itskaaryan7 because we are using a map
@@Dontpushyour_luck this can be simply avoid by finding the leftmost and rightmost column length.
done before you explaining... that's the level of ur teaching... u make us think nd do it ourselves.... Thanks a lot #saviour
Thanks Striver Bhaiya for Uploading such high quality content for free on TH-cam it feels more than any paid content.
This explanation is astounding! The explanation of why recursive traversal is ineffective in this situation struck a deep chord.
Truly AMAZING explanation. You're such a KING!
the change we can do is ig...we can carry another parameter as depth...and we will create a map like map ...where the int inside the pair is the depth...so we only update the vertical if the current depth is greater than the stored depth....maybe this should work
It has to work but I tried it and I can't implement it myself
Best DSA content. Miles and leagues ahead of other channels! 🙌🙌🙌
In top view of the tree we check before adding to the map if there is an existing node from that particular line number , simply remove that checking condition that's all your code for bottom view is done :)
Being able to solve these question on my own coz of your previous explanations. Thankyou Striver!!!
dhanybad bhaiya aapke wajah se hum ab tree pe chadna start kar diya hai thoda thoda
I was just doing by recursion without thinking of the last example which u have shown ..thank you so much ❤️
As soon as you said vertical order traversal, I closed the tab and solved the question. And I got to learn about vertical order traversal, 🤣
Great explanation sir. Masterpiece !
Thanx bhaiya mujhe bottom view samjne me dikkat jari thi. Ye video me first attempt me samaj gaya.
Completed 24/54(44% done) !!!
I solved this question on my own after doing last q on finding top view , just came here to see what better can be done .
Using recursion can also be solved
void preorder(Node *root, int vlevel, int hlevel, map &m)
{
if (root == 0)
return;
if (m.find(vlevel) == m.end() || m[vlevel].first data};
preorder(root->left, vlevel - 1, hlevel + 1, m);
preorder(root->right, vlevel + 1, hlevel + 1, m);
}
vector bottomView(Node *root)
{
map m;
preorder(root, 0, 0, m);
vector res;
for (auto ele : m)
{
res.push_back(ele.second.second);
}
return res;
}
Thanks @striver for amazing content
Shouldn't the worst case time complexity be O(n Logn) in case of skewed tree, because of map/TreeMap?
Yeah i have left the tree map complexity to be added by the user
The best coding channel on TH-cam!
Understood ❤
very easy to undertsnad the logic after watching previous top view video,thanks a lott
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understtooooooooooddd
THansk You Bhaiya
i was confused about depth traversal , now it is clear
Awesome Lecture
understood 😇
explained very well, sirf apke video se bfs theek se samaj paya.
also had a doubt, why cant we use recursion(postorder traversal) with map? once we map for each horizontal distance, we can ignore other nodes, during traversal.
Same questipn , why complicate things , no need to use level order traversal
if we use unordered_map and keep track of leftmost element we can actually keep the complexity to minimum . map has push and find complexity of log(N).....even though we are not pushing each element but we are checking whether to push or not for each element .
UNDERSTOOD;
Thank you so much.
THANK YOU SO MUCH , YOUR EXPLANATION WAS VERY MUCH UNDERSTANDABLE
UNDERSTOOD
Best DSA content, top notch
Recursive wala part was excellent 🔥🔥🔥👌👌👌
// code for recrsive approach,just keep track of row number.
//Structur of map: colum_no={data,rownumber}
//if row number is larger than previous stored data,then replace.
void f(BinaryTreeNode * root, int row,int col,map &mp){
if(root==0)return;
if(row>=mp[col].second)
mp[col]={root->data,row};
f(root->left,row+1,col-1,mp);
f(root->right,row+1,col+1,mp);
}
tysm sir
Very well explained sir
Understood! So wonderful explanation as always, thank you very much!!
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]
for sorting the keys it will take nlogn right!!!!!
bfs dfs both work smooth !
The time complexity should be O(nlogn) right ?
bcs of sorted function used in python.
pls some correct me if i am wrong
Very high Quality content !
I have solve the question via both level order as well as DFS still I am excited to see striver solution
Understood very well .Thank you bhaiya amazing trees playlist keep doing this bhaiya :)
Undertsood
Thank you sir
Recursive soln: [JAVA]
class Pair {
int level;
int nodeVal;
Pair (int level, int nodeVal) {
this.level = level;
this.nodeVal = nodeVal;
}
}
public class Solution {
public static List bottomView(TreeNode root) {
// Write your code here.
TreeMap map = new TreeMap();
travel(0, 0, root, map);
List ans = new ArrayList();
for (Pair pair: map.values())
ans.add(pair.nodeVal);
return ans;
}
static void travel(int x, int y, TreeNode cur, TreeMap map) {
if (cur == null) return;
if (!map.containsKey(x))
map.put(x, new Pair(y, cur.val));
else if(map.get(x).level
understood bro
it can be solved in O(n) also , you didn't covered that?
wow nice approach 😀😀
understood
You have used map and map sort the Data then How Time Complexity is O(N) ??
Why not O(Nlogn) ??
Basically in java its o(1), hence i have written, you can use n log n if using c++ and not unordered map
@@takeUforward But u have used treeMap which has time complexity of O(logn) in worst case while inserting elements so the time complexity will O(nlogn)
11:44 we need right one only in BV of BT...so recursive approach would work here...right?
thanks sir , great efforts
Understood,able to solve by myself
or we could just do top view but remove the if statement which checks if the line already is there in the map, as we are essentially trying to put the latest value for a particular vertical line
thanks ,u r doing great job
Understood . Great series
Striver is just awesome
Thanks! Understood!
Huge respect...❤👏
nice explanation, clean code
The solution may be incorrect for the following tree:
root = Node(0)
root.left = Node(1)
root.right = Node(2)
root.left.right = Node(3)
root.right.left = Node(4)
Actual output: 1 4 5
Expected Output: 1 3 4 5
Output is incorrect because the distance of {node, node.left.right, node.right.left} for any node is the same. So, both node.left.right and node.right.left should be added to the output, instead of just selecting node.right.left.
There is no node with value (5) inserted into the tree according to the tree provided, and according to the tree the output should be 1 4 2. Yes vertical of {root, root->left->right, root->right->left} is same, but the value of {root->right->left} would be selected as it hides the 2 nodes {root, root->left->right} above it. Hope it helps!
Explained well, good job buddy... keep doing videos✨
completed lecture 23 of free ka tree series.
Thank you bhaiya
thank you striver
in line 14---Node*node=it.first
then why we are doing ans.push_back(it.second)???
how does it ensure that the values stored in the hashmap at last are sorted.I had to apply a seperate function for sorting according to hd
thank you so much bhaiyaa
💚
In case anyone needs help:
// Problem link: practice.geeksforgeeks.org/problems/bottom-view-of-binary-tree/1
// Approach 1: Recursive Approach:
class Solution {
public:
void bottomViewUtil(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 data};
}
bottomViewUtil(root->left, distance - 1, height + 1, mp);
bottomViewUtil(root->right, distance + 1, height + 1, mp);
}
vector bottomView(Node *root){
map mp; // {distance, {level, ans}}
int distance = 0; // How farther away towards left/right from the root
int height = 1;
bottomViewUtil(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 bottomView(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();
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;
}
};
// Time Complexity: O(n)
// Space Complexity: O(n)
in love with your content!!!
UNDERSTOOD
we love your content and we love you ....🖤
Great Bhaiya 🙏🙏
public List bottomView(Node root)
{
TreeMap map = new TreeMap();
Queue q = new LinkedList();
q.add(new Pair(root, 0));
while(!q.isEmpty())
{
Pair p = q.poll();
Node node = p.node;
int x = p.num;
if(!map.containsKey(x))
map.put(x, node.data);
else
map.put(x, node.data);
if(node.left!=null)
q.add(new Pair(node.left, x-1));
if(node.right!=null)
q.add(new Pair(node.right, x+1));
}
List list = new ArrayList();
for(int val : map.values())
list.add(val);
return list;
}
WORKS 👍
Tq sir
VIDEO aagya 🙌✌️
understood
Understood
Understood 👍
sir,
Moj kar de
But hash maps in Java are not sorted they put the values in random in if we want to sort it we need to use a comparator and which will again add up time complexity
use treemap
solved without watching the vidd
Understood!
Can we do it in O(n) time and O(n) space ??
❤❤❤❤❤❤❤
Dont we need to sort the map here in java?
2:20 -3:55
My dfs version :
void hlp(Node*root,int hd,int lvl, map&mp){
if(!root)return ;
if(!mp.count(hd) or lvl >= mp[hd].first){ // = is very important as it prints the later node if they have the same coordinated
mp[hd] = {lvl,root->data};
}
hlp(root->left,hd-1,lvl+1,mp);
hlp(root->right,hd+1,lvl+1,mp);
}
vector bottomView(Node *root) {
// Your Code Here
if(!root)return {};
vectorans;
mapmp;
if(!root->left and !root->right)return {root->data};
hlp(root,0,0,mp);
for(auto &el : mp){
ans.push_back(el.second.second);
}
return ans;
}
Time : O(nlogn)
Space : O(n)
But in map duplicate key not allowed ,so how the value overwrite in this program
did you got it . why ?
understooood. thanks :)
Instead of bfs, I try to implement using dfs but it gives me the wrong answer
map m;
void dfs(Node* root, int cnt)
{
if (root == NULL)
return ;
m[cnt] = root->data;
dfs(root->left, cnt-1);
dfs(root->right,cnt+1);
}
vector bottomView(Node *root)
{
m.clear();
dfs(root,0);
vector v;
for (auto x : m)
v.push_back(x.second);
return v;
}
aagya aagyaa...