L24. Right/Left View of Binary Tree | C++ | Java

[@takeUforward]

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

[@rishabsharma5307]

Waiting for Morris Inorder Traversal

[@takeUforward]

@@rishabsharma5307 That will be the best video of this series.

[@rishabsharma5307]

@@takeUforward can't wait for it 🤩

[@rohan8758]

For Left Side View , call the recursive function with the left node and then with the right node . f(node->left, level+1); f(node->right, level+1);

[@kuldeepkushwah565]

Thank you striver for all your effort, your content is worth more than any paid courses. This Chanel is full of treasure.

[@sarathchandra941]

Hiidden behind the youtube recommendation algo..🥺 #open sesame😎 -- tree ka free series treasure will be urs🤭

[@krishnasudan3410]

My iterative approach.. thanks Bhaiya for everything.. Such a gem in coding community vector rightView(Node *root){ vector res; if(root==NULL) return res; queue q; q.push(root); while(!q.empty()){ Node *temp = q.front(); res.push_back(temp->data); int size = q.size(); for(int i=0;iright!=NULL) q.push(curr->right); if(curr->left!=NULL) q.push(curr->left); } } return res; }

[@gautamjh]

In your code, you should push left node before the right node in the queue in for loop

[@isheep9025]

@@gautamjh no its correct for right view

[@rutwikmore7462]

bro I also wrote the exact same code..😄😄

[@uRamPlus]

self notes: 🚀 for every level, the first node (on the right side) will be our right side view 🚀 if the level of the tree == my vector's size, I need to push it into my vector 🚀 if at any point we reach a null node, we just need to return (base case)

[@moksh455]

That code is self explanatory no need to maintain notes

[@ritwikdurga3855]

@@moksh455go touch grass

[@anmolswarnkar7707]

Amazing explanation! I like the fact that you go step by step (like a compiler would) over the example. Keep posting these videos!

[@VishalGupta-xw2rp]

What i came up was that (before watching video) For(Right View) Use Vertical order only This time instead of left - 1, we will increase both and Mark each node *levels* not their *vertical* left + 1, right + 1 Now simply as we go we will store the latest level by m[level] = node->data. Because of map property, it will itself ensure that all the latest one will be there so overwrites the previous But what a technique and Amazing approach.... Man when will i begin to think like that ♥️🔥

[@priyankarkoley]

I believe that will end up with nlog(n) time complexity.

[@blitzkrieg5454]

I feel so lucky to have a teacher like you, thanks a lottt!!!

[@shubh13799]

your explanation techniques are phenomenal, clear concepts and concise code. Loving the way you code.

[@Dontpushyour_luck]

so clever technique of using recursion and size of data structure to check if it is the first node that we came to in this level. no wonder you are candidate master on codeforces!

[@samarthsingh2705]

I first watched the video of apna college youtube channel where they discussed the iterative method using level order traversal. This code here in this video is very short and also very well explained by striver. Thanks TUF for such amazing content.

[@4mulate]

My iterative approach which was before I watched your explanation: //just push to ans vector when we are at last node in the queue. class Solution { public: vector rightSideView(TreeNode* root) { vector ans; if(root==nullptr) return {}; queue q; q.push(root); while(!q.empty()){ int size = q.size(); for(int i=0;ival); } q.pop(); if(front->left!=nullptr) q.push(front->left); if(front->right!=nullptr) q.push(front->right); } } return ans; } };

[@animeshbarole]

if(level==ds.size()) ans.push_back(node->val) is just Mind blowing technique ....... Take a bow Striver .

[@falgunitagadkar4097]

Your approach to solve problems is just commendable👏👏 Thanks for providing so valuable content for free! Again...the same thing...Hats off to you Striver ✌

[@HimanshuSingh-hd8of]

//Implemetation of above approach Initially we pass 0 in level res is data structure that we are using for storing the elements void find_right_view(Node *root,vector&res,int level){ if(root==NULL){return ;} if(level==res.size()){ res.push_back(root->data); } find_right_view(root->right,res,level+1); find_right_view(root->left,res,level+1); }

[@ojasthengadi9681]

hey can you please explain why the level becomes 0 once we reach to root node before travsersing to left

[@yogeshjoshi781]

I saw the video of top view, then I solved botom view on my own then I just changed line-1 to line+1 in that bottom view solution and I got this answer right. just a single change thank you striver

[@ArushiRoy2823]

Oaw , what an amazing explanation and logic behind the code is superb 🥺

[@divyansh2212]

Easy solution for left view level order traversal: #include using namespace std; vector getLeftView(TreeNode *root) { if (root == NULL) return {}; vector ans; queue q; q.push(root); while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; i++) { auto front = q.front(); q.pop(); if (i == 0) ans.push_back(front->data); if (front->left) q.push(front->left); if (front->right) q.push(front->right); } } return ans; }

[@rajnishism2898]

For Left Side View , call the recurssive function with left node and then with the right node . f(node->left, level+1); f(node->right, level+1);

[@rishabhinc2936]

i could have never ever thought of comparing level and ds size.striver ur insane man

[@akcGaming-e5h]

Loved it thank you so much 😃

[@siddhantgupta4773]

Level Order Traversal Solution for reference: vector rightSideView(TreeNode* root) { vector ans; if(!root) return ans; queue q; q.push(root); while(!q.empty()) { int size = q.size(); for(int i = 0;i < size;i++) { TreeNode *temp = q.front(); q.pop(); if(i == size-1) ans.push_back(temp->val); if(temp->left) q.push(temp->left); if(temp->right) q.push(temp->right); } } return ans; }

[@dronrahangdale2361]

there should right first in the for loop for rightside view rest all is correct 🙂

[@avicr4727]

@@dronrahangdale2361 he put i= size-1 if i=0 then right should come first

[@ScienceSeekho]

// BFS - Iterative - keeping a last variable. TC: O(N) SC: O(N) // -- In worst case all bottom nodes will be stored in queue, to avoid this we go with DFS vector rightSideView(TreeNode* root) { vector ans; if(root==NULL) return ans; queue q; q.push(root); while(!q.empty()) { int n = q.size(); int last; while(n--) { TreeNode* tn = q.front(); q.pop(); if(tn->left) q.push(tn->left); if(tn->right) q.push(tn->right); last = tn->val; } ans.push_back(last); } return ans; }

[@rohandevaki4349]

very simple approach and great explaination, how do you get these approaches? i wasnt able to get any approach even after trying so much.

[@dheepakraaj8352]

Understood bhaiya thank you. Level Order Traversal Apporach: During level order traversal ,we had one size variable which tells the size of queue at each level so if i==size-1; then that element is the last element of that level so we can push it into the data structure. Is this approach right bhaiya?

[@takeUforward]

Yeah.. correct.

[@dheepakraaj8352]

@@takeUforward thank you bhaiya 💖😃

[@PalakMittal]

In case anyone want iterative method 😅 class Solution { public: //Function to return list containing elements of right view of binary tree. vector rightView(Node *root) { // Your Code here vectorres; if(!root) return res; queueq; q.push(root); while(!q.empty()){ int n=q.size(); for(int i=0;idata); } Node* node=q.front(); q.pop(); if(node->right) q.push(node->right); if(node->left) q.push(node->left); } } return res; } }; PS: Recursive one was just mind blowing 😍😍

[@Sujit13484]

Good work. I like the way you explain each problem. Once change we can do. I think we can do it without using Stack also by keeping a counter for max level reached from right tree. Here is code below. class Solution { int maxLevelSoFar = -1; public List rightSideView(TreeNode root) { List result = new ArrayList(); rightRecursive(root, 0, result); return result; } private void rightRecursive(TreeNode root, int level, List result) { if(root == null) { return; } if(level > maxLevelSoFar) { result.add(root.val); } rightRecursive(root.right, level + 1, result); rightRecursive(root.left, level + 1, result); maxLevelSoFar = Math.max(maxLevelSoFar, level); } }

[@maradanikhil6882]

Here is the level order traversal for right side view: class Solution { public: vector rightSideView(TreeNode* root) { queueq; q.push(root); vectorans; if(root==NULL) return ans; while(!q.empty()){ int size=q.size(); int a=0; for(int i=0;ival; if(node->left) q.push(node->left); if(node->right) q.push(node->right); } ans.push_back(a); }return ans; } };

[@iamnottech8918]

I solved this on my own using horizontal line , I was thinking that recursion will work on this came here to conform .. thanks...

[@ssaha7714]

Too good. Amazed to see the explanation… clear and to the point..

[@pranav4969]

Even if the tree is perfectly balanced for level order, the maximum number of nodes at any level will always be less than log(N) - 1. So level order takes almost same space as recursive for balanced trees. And also level order takes less space for skewed trees. So space wise , level order is better than recursive

[@tear7934]

how is it log(N) - 1 can you please explain

[@prabhakaran5542]

Understood ❤

[@apmotivationakashparmar722]

Thank you so much Striver ! .

[@BTEEELavkushYadav]

Millions of thanks to you bro you make my concept crystal clear I have subscribed ur channel instant

[@NavyasriThalluri]

The way how you use recursion is damn good

[@ishangujarathi10]

awesome logic of level==ds.size(), unserstood in depth !!!

[@anishamajumder1940]

for left side view - use preorder traversal and get the first element

[@maneetrajgupta]

correction... iterative way's space complexity can be optimized to O(H).

[@stormshadow76]

This is the most brilliant solution !!!!!!! Amazing !!!

[@sujan_kumar_mitra]

Understood! Nice intuition to figure out if we are visiting the depth first or not

[@per.seus._]

UNDERSTOOD

[@prajaktakapoor7520]

Great solution sir!! Really impressed

[@SohamDutta222]

Man, You are the best.. best explanation

[@sharmanihal99]

This DFS Solution was more intutive for me. class Solution: def __init__(self): self.rightmost_values = defaultdict(int) def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] self.reversePreorder(root, 0) return self.rightmost_values.values() def reversePreorder(self, root, level): if not root: return if level not in self.rightmost_values: self.rightmost_values[level] = root.val # Traverse right subtree first for getting rightmost values self.reversePreorder(root.right, level + 1) self.reversePreorder(root.left, level + 1)

[@sifatsamir0076]

nice explaination ❤ Love from Bangladesh❤

[@cinime]

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

[@areebahmadsiddiqui2648]

I am watching your channel the very first time and maaaaan you are damn good thanq for this

[@pranalipardeshi7748]

for 11:49 we can keep same pre order traversal i.e first left and then right

[@guneetgupta3356]

for left view tree, you should go for root left right raversal

[@sachinvarma9949]

that was a mind blown solution

[@mohit7717]

for left view :- Root Left Right ... I think inorder will work .. I just comment after you told to comment down how to do left view....

[@tanaykamath1415]

I managed to solve this using an iterative approach but the soln. was complex af!, how do you manage to come up with such easy solns. 🙈🙈

[@U-DAY]

bro i never saw this much like amazing explanation ..... superb awesome u are.... loving ur teaching bro........................

[@lifehustlers164]

Completed 25/54(46% done) !!!

[@avinashgupta2308]

Amazing approach! and definitely the way you teach is just ❤

[@anmolsingh3482]

%Function for LeftView func(Node* node, int level) { if(node == NULL) return; if(level == ds.size()) ds.push_back(node); func(node->left, level+1); func(node->right, level+1); }

[@sharda16april]

Amazing Striver.. Such an amazing explanation. I used BFS and it was not as clean as your code.

[@nitunsingh6986]

We can use set data structure over here to store right view only same for left view.

[@shreyasvishwakarma8979]

11:39 just exchange f ( node -> right ) and f ( left->left )

[@golangNinja29]

We could have used , map instead of array, in which if key( level) already exists then ignore And iteration will be same as shown in video

[@krishnaradhey2814]

On GFG if you traverse via QUEUE it gives segmentation fault.... CODE:- /* A binary tree node struct Node { int data; struct Node* left; struct Node* right; Node(int x){ data = x; left = right = NULL; } }; */ //Function to return a list containing elements of left view of the binary tree. vector leftView(Node *root) { // Your code here vectorans; vectorvec; queuequ; qu.push(root); while(qu.empty() != true) { int size = qu.size(); vectordemo; while(size--) { Node* temp = qu.front(); qu.pop(); demo.push_back(temp->data); if(temp->left != nullptr)qu.push(temp->left); if(temp->right != nullptr)qu.push(temp->right); } vec.push_back(demo); } for(int i = 0 ;i

[@lakshsinghania]

Iterative sol for the right side view of the binary tree class Solution { public: vector rightSideView(TreeNode* root) { vector ans; queue q; q.push(root); if(root == NULL) return ans; while(!q.empty()){ TreeNode* node = q.front(); ans.push_back(node -> val); int s = q.size(); for(int i =0; i right != NULL) q.push(node -> right); if(node -> left != NULL) q.push(node -> left); } } return ans; } };

[@jonu.1504]

Recursive is easy than Iterative. Which one is good performance wise?

[@divyan154]

instead of reverse preorder traversal do traditional preorder and rest same

[@DeadPoolx1712]

UNDERSTOOD;

[@raghavkhandelwal1094]

for left view Instead of Reverse pre order trav. i.e, RRL take preorder trav. as the approach i.e., RLR

[@takeUforward]

yes correct, amazing!

[@harshopes]

Note to self: left side view call a recursve function with the root,list,level leftViewHelper(root.left, list, level+1); leftViewHelper(root.right, list, level+1); visaVersa for right side view

[@nikhilnagrale]

// Level Order Traversal Variation // Time Complexity - O(N) // Space Complexity - O(N) class Solution { public: vector rightSideView(TreeNode* root) { vector res; if (!root) return {}; queue q; q.push(root); while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { TreeNode* curr = q.front(); q.pop(); if (i == 0) res.push_back(curr->val); if (curr->right) q.push(curr->right); if (curr->left) q.push(curr->left); } } return res; } };

[@adityajain1205]

This code is for left view

[@nikhilnagrale]

@@adityajain1205 bruh if you think that way, then you didn't understand the concept. Watch video again

[@ArvindYadav-gy7fj]

@@adityajain1205 i think it is for right view

[@VivekSharma-eh2tv]

for the left view we, will call the recursive function for the left node and then the right node -> the logic of returning remains same but the direction of movement alters .. am i right @takeUforward

[@Rajat_maurya]

i bow my head... bhagwan apko sari khushiya de app itta bada kam free m kar rahe

[@clumsyshots5558]

Iterative Approach vector rightSideView(TreeNode* root) { vector res; if(!root) return res; queue q; q.push({root,0}); while(!q.empty()){ auto it=q.front(); q.pop(); TreeNode* node=it.first; int level = it.second; if(res.size()==level){ res.push_back(node->val); } if(node->right) q.push({node->right,level+1}); if(node->left) q.push({node->left,level+1}); } return res; }

[@bhashkarbelwal4116]

wow thanks a lot for the explanation '

[@adebisisheriff159]

Thanks so much Striver !!!!!

[@prasadprashantb.4001]

You are amazing bro❤ keep it up🙌

[@codeloader3921]

thank you sir

[@Shivi32590]

thank you

[@nithishkumarreddygorre1768]

traverse in root,left,right

[@tusharkumar4036]

For Left View C++ Code : void left(Node *root,vector&m,int l){ if(root==NULL) return ; if(m.size()==l) { m.push_back(root->data); } left(root->left,m,l+1); left(root->right,m,l+1); } vector leftView(Node *root) { // Your code here vectorv; int level=0; left(root,v,level); return v; }

[@devanshmesson2777]

I think the space complexity for recursive approach will be O(N), because we end up traversing the whole tree, So, there will be N recursive calls.

[@yashtarwe6878]

very good explanation and approach

[@urdaddy8520]

Initially I was thinking to use level order traversal using deque, and then store last value of deque in our answer; can it be correct?? I'm confused...

[@varunvishwakarma9689]

In-Recursive way: if we take Complete Binary Tree (No-skewed) then also Auxilary space will be O(N) only na?......and not O(h) because its traversing to every node and for each node stack space is alloted in backend

[@stark3585]

Vey good concept of vertical lines. Keep going bro....

[@bollamajay9794]

python code: from collections import deque def rightView(self,root): if root is None: return [ ] q=deque() q.append(root) res=[] while q: count=len(q) for i in range(count): node=q.popleft() if i==(count-1): res.append(node.data) if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) return res

[@ManishYadav-dq9xm]

shouldn't the level count also increase if it returns to left side after checking that right is null?

[@bhalulal5947]

Same I have doubt?? Does anyone has solution for this??

[@ssplusultra8645]

why arent u doing morris traversal? space would be O(1)

[@Kaushik846]

Awesome technique and explanation!!!

[@Prateek03]

Thank you striver, you made things easy for us 🔥

[@ayushkushwaha171]

we can make use of map to solve this as well just like your previous top & bottom view questions

[@abhishekkumarjhariya1340]

for the left view we will simply take the normal preorder (root, left, right) and rest of the things will remain same.

[@gourangpathak4443]

Yeah I also think the same

[@omkarshendge5438]

yeah same i also thought of this!

[@sourabh258]

Excellent stuff, thanks for such a simple explanation!

[@captainakash8914]

for left view just change the traversal order

[@bollamajay9794]

python code: def LeftView(root): if root is None: return [ ] q=deque() q.append(root) res=[] while q: count=len(q) for i in range(count): node=q.popleft() if i==0: res.append(node.data) if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) return res

[@hanish6713]

whats time complexity of the code ans also space complexity?

[@shaiksoofi3741]

understod

[@SohamPatil-k9z]

The second approach will acutally not work for in some cases . for example take the same binary tree in video and suppose 7 has a one left child 19 and 19 has one more left child 20,and also suppose 5 has one right child 21 and 21 has one right child 22.So in this case the 20 will be rightside view for level 5 which is wrong because 22 will be the rightmost for level 5 . Correct me i am wrong somewhere .

[@tejaswaniguttula5961]

This is what I came up for left view using level order traversal:- vector leftView(Node* root) { vector ans; if(root == nullptr) return ans; map mpp; queue q; q.push({root, 0}); while(!q.empty()){ auto p = q.front(); q.pop(); Node* node = p.first; int line = p.second; mpp[line] = node -> data; if(node -> right){ q.push({node -> right, line + 1 }); } if(node -> left){ q.push({node -> left, line+1}); } } for(auto it: mpp ){ ans.push_back(it.second); } return ans; }

[@tejaswaniguttula5961]

For right view using level order traversal :- vector rightSideView(TreeNode* root) { vector ans; if(root == nullptr) return ans; map mpp; queue q; q.push({root, 0}); while(!q.empty()){ auto p = q.front(); q.pop(); TreeNode* node = p.first; int line = p.second; mpp[line] = node -> val; if(node -> left){ q.push({node -> left, line+1}); } if(node -> right){ q.push({node -> right, line + 1 }); } } for(auto it: mpp ){ ans.push_back(it.second); } return ans; }

[@sonakshibajpai6445]

understood

[@sahilsaharn5963]

So we have to keep track of max level if it filled we skip the other node and if not we include it

[@akhilakapse204]

Please keep at it bro. These videos are super helpful!

[@RupamSasmalYt]

// Level order Traversal: if(root==NULL) return {}; vector res; queue q; q.push(root); while(!q.empty()){ int size=q.size(); for(int i=0;ival); if(it->right!=NULL) q.push(it->right); if(it->left!=NULL) q.push(it->left); } } return res;

[@suvhamdas2049]

preorder solution will do as we need the left node first.