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)
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 ♥️🔥
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!
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 ✌
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; } };
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.
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; }
//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); }
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); } }
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; } };
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)
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...
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?
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
// 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();
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
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
can someone explain why space complexity is O(h) the data which we are storing in data structure is the output so we dont consider that, then it should be O(1) right
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;
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; } };
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
Waiting for Morris Inorder Traversal
@@rishabsharma5307 That will be the best video of this series.
@@takeUforward can't wait for it 🤩
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)
That code is self explanatory no need to maintain notes
@@moksh455go touch grass
Amazing explanation! I like the fact that you go step by step (like a compiler would) over the example. Keep posting these videos!
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);
Thank you striver for all your effort, your content is worth more than any paid courses.
This Chanel is full of treasure.
Hiidden behind the youtube recommendation algo..🥺
#open sesame😎 -- tree ka free series treasure will be urs🤭
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 ♥️🔥
I believe that will end up with nlog(n) time complexity.
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;
}
In your code, you should push left node before the right node in the queue in for loop
@@gautamjh no its correct for right view
bro I also wrote the exact same code..😄😄
I feel so lucky to have a teacher like you, thanks a lottt!!!
your explanation techniques are phenomenal, clear concepts and concise code. Loving the way you code.
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!
Too good. Amazed to see the explanation… clear and to the point..
i could have never ever thought of comparing level and ds size.striver ur insane man
Understood! So amazing explanation as always, thank you very much!!
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 ✌
Understood! Nice intuition to figure out if we are visiting the depth first or not
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;
}
};
Amazing approach! and definitely the way you teach is just ❤
Millions of thanks to you bro
you make my concept crystal clear
I have subscribed ur channel instant
Oaw , what an amazing explanation and logic behind the code is superb 🥺
Excellent stuff, thanks for such a simple explanation!
Great solution sir!! Really impressed
bro i never saw this much like amazing explanation ..... superb awesome u are....
loving ur teaching bro........................
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.
This is the most brilliant solution !!!!!!! Amazing !!!
if(level==ds.size()) ans.push_back(node->val) is just Mind blowing technique ....... Take a bow Striver .
Man, You are the best.. best explanation
The way how you use recursion is damn good
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;
}
that was a mind blown solution
nice explaination ❤ Love from Bangladesh❤
You are amazing bro❤ keep it up🙌
Vey good concept of vertical lines. Keep going bro....
Thank you striver, you made things easy for us 🔥
Thanks so much Striver !!!!!
wow thanks a lot for the explanation
'
thank you for the dry run explanation!! amazing
//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);
}
hey can you please explain why the level becomes 0 once we reach to root node before travsersing to left
Please keep at it bro. These videos are super helpful!
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);
}
}
I am watching your channel the very first time and maaaaan you are damn good thanq for this
Amazing Striver.. Such an amazing explanation. I used BFS and it was not as clean as your code.
Awesome technique and explanation!!!
Amazing Explaintaion 👏❤️
Keep Posting These kinds of Content 🙏👍
Very well explained 👍
awesome logic of level==ds.size(), unserstood in depth !!!
UNDERSTOOD
thank you
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;
}
};
Amazing explanation!
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)
We can use set data structure over here to store right view only same for left view.
Amazing Explanation 🔥🔥
Amazing video! 👏🏻🙌🏻
Which tool you are using to write and sketch here?
Simple nailed it 👏
very simple approach and great explaination, how do you get these approaches? i wasnt able to get any approach even after trying so much.
Amazing explanation! love u bro.. keep posting like that
Nice
Awesome explanation and crisp code
very good explanation and approach
Thank you for these series
I solved this on my own using horizontal line , I was thinking that recursion will work on this came here to conform .. thanks...
Amazing content!!!
i bow my head... bhagwan apko sari khushiya de app itta bada kam free m kar rahe
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...
understood
well explained bhaiya!
great solution thanks :)
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?
Yeah.. correct.
@@takeUforward thank you bhaiya 💖😃
// 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;
}
};
This code is for left view
@@adityajain1205 bruh if you think that way, then you didn't understand the concept. Watch video again
@@adityajain1205 i think it is for right view
understod
%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);
}
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. 🙈🙈
for left side view - use preorder traversal and get the first element
Completed 25/54(46% done) !!!
great explanation!
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
how is it log(N) - 1 can you please explain
Thank you bhaiya. Wonderful teacher 👏
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;
}
there should right first in the for loop for rightside view rest all is correct 🙂
@@dronrahangdale2361 he put i= size-1 if i=0 then right should come first
// 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;
}
for 11:49 we can keep same pre order traversal i.e first left and then right
for left view tree, you should go for root left right raversal
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
11:39 just exchange f ( node -> right ) and f ( left->left )
Recursive is easy than Iterative. Which one is good performance wise?
how will the value of level reduce
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
correction... iterative way's space complexity can be optimized to O(H).
beautifully explained
can someone explain why space complexity is O(h) the data which we are storing in data structure is the output so we dont consider that, then it should be O(1) right
O(H) is the auxiliary space for the recursive call stack
why the level won't increase when we traverse the left side of the tree?
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 😍😍
traverse in root,left,right
why arent u doing morris traversal? space would be O(1)
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;
}
};
for left view
Instead of Reverse pre order trav. i.e, RRL take preorder trav. as the approach i.e., RLR
yes correct, amazing!
Amazing content bro!!!
// 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;
instead of reverse preorder traversal do traditional preorder and rest same
nice approach striver
we can make use of map to solve this as well just like your previous top & bottom view questions
great explanation