Binary Tree Right Side View - Breadth First Search - Leetcode 199

[@NeetCode]

Tree Question Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@littlebox4328]

Very good explaination thanks, do you mind to explain the dfs approach for this?

[@rathnashakthi5012]

I can't thank you enough for what you're doing!! You never know how much you're helping a developer who is restarting her career after a huge break!! I do follow few other KZbinrs, but Yours is the BEST!! Thank you so much!! keep doing what you're doing.

[@rkwong792music]

Another good vid! Thanks! This problem is very similar to LC 102 - Binary Tree Level Order Traversal. I found this solution which is similar to LC 102 a little easier to remember: res = [] q = collections.deque() if root: q.append(root) while q: res.append(q[-1].val) for i in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return res

[@DmitriyKl]

That's the solution I came up with. q[-val] to grab the rightmost node's value is the key here

[@hwang1607]

i came up with this as well, definitely makes it easier if you've done the previous question

[@syafzal273]

I came up with the same after doing level order and I think it is easier to read

[@ancientgearsynchro]

I took one look and at this problem and knew I was missing something and it was that the new example image does not explain what it is looking for. Thanks for the clarification.

[@swaroopacharjee2767]

Really thank you for the solution. I would like to add my little optimisation to your solution. class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] q, res = [root], [] while q: for i in range(len(q)): node = q.pop(0) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(node.val) return res

[@sutheerth8479]

why is it that for me, in gfg, im not able to use collections.deque()? "collections is not defined" is the error i receive, even after importing the module

[@erickmercado1711]

You cant give pop(0) an argument if you use a deque, he is manually returning the leftmost node to pop so with a dec you instead do popleft()@@sutheerth8479

[@erickmercado1711]

Also you should use None instead of [ ] as it wont handle the None case correctly

[@thelookofdisapproval8234]

I did this a while ago, using DFS. just keep track of current level, and largest level you encountered yet.

[@camoenv3272]

Here's a recursive DFS solution in Python, since the video covered BFS! def rightSideView(self, root: Optional[TreeNode]) -> List[int]: res = [] def dfs(node, level): if not node: return if len(res)

[@shadyplaysgoodgames]

thanks pal

[@stephentomaszewski8501]

super easy solution for me was to use bfs, an output list and a current level list. Inside the while loop initialize the current level list so it resets at every level. Inside the for loop append the current level list with each node value. At the exit of the for loop at before you repeat the while loop, pop the current level stack and add it to the output list.

[@bigboimoe]

That's what I had as well, much more readable code and intuitive answer that you can come up with during an interview.

[@mohamadilhamramadhan6354]

Depth first search solution: def rightSideView(root): result = [] def dfs(node, depth): if not node: return False if depth > len(result): result.append(node.val) dfs(node.right, depth + 1) dfs(node.left, depth + 1) dfs(root, 1) return result

[@Cloud-577]

I think it also easier to instead of traversing from left to right we traverse from right to left and append the first node val of each level. we can get the first node using a for loop that runs for the size of the cur q

[@kuoyulu6714]

I agreed. I did it right to left first and got it correct, but was wondering why left to right will also give the correct answer, then I realize the right node is being replace again and again in the for loop until the last none null node. I find right to left is easier to understand for me as I am just starting to learn.

[@FirePizza94]

I gotta say, love your videos, makes understanding algos much easier as someone who is self taught! Although , I’m having a hard time understanding while the right side flag is necessary given the code

[@shatakshisharma8557]

@NeetCode while the right side flag is necessary given the code same. can't see code to find right most element.

[@romo119]

Makes more sense for me to do null check in the beginning, then at each iteration of the while loop the right side is always the value to be appended to ret. Then only add non null nodes to the queue while popping

[@The6thProgrammer]

100% this is what I did as well. More intuitive

[@Japakak]

Version where you don't need to check for null/None values: class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if root is None: return [] q = deque([root]) right_side = [] while q: for i in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) right_side.append(node.val) return right_side

[@darr915]

I simply enqueued the right children first before the left, which means that the first node that I dequeue for a level is always the rightmost node.

[@SAVAGE_AF_]

me 2!

[@villurikishore7779]

This is the best solution I've seen and very crisp explanation.

[@gulshankumar17]

void rightSideViewHelper(TreeNode* node, vector &result, int level) { if(node) { if(result.size() val); } rightSideViewHelper(node->right, result, level + 1); rightSideViewHelper(node->left, result, level + 1); } } vector rightSideView(TreeNode* root) { vector result; rightSideViewHelper(root, result, 0); return result; }

[@numberonep5404]

Crisp explanation as usual :3 muchas gracias Another solution i came up with after waaay too much time: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: res = {} def dfs(root, depth): if root: if depth not in res: res[depth] = root.val dfs(root.right,depth+1) dfs(root.left, depth+1) dfs(root,0) return list(res.values())

[@SAVAGE_AF_]

the dedication which you put in to create the videos is impressive! Please don't stop, ever! Thank you so much!

[@sebselassie]

I think this solution is a bit easier. We just have an answer array and always replace the value at the current level we are at (or append). Since we are going left first, we make sure the answer will always have the righter most values: class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: queue = [] if root: queue.append((root, 0)) ans = [] while len(queue) > 0: node, level = queue.pop(0) if len(ans)

[@_control_]

Here is the dfs solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: res = [] def dfs(root, h): if root: if h >= len(res): res.append(root.val) else: res[h] = root.val dfs(root.left, h+1) dfs(root.right, h+1) dfs(root, 0) return res

[@chingiskhant4971]

Here's a dfs in python I'm proud I came up with: def rightSideView(root): res = [] def dfs(root, depth): if not root: return if depth == len(res): res.append(root.val) dfs(root.right, depth+1) dfs(root.left, depth+1) dfs(root, 0) return res

[@EricProgramming]

Easy Java Solution: class Solution { public List rightSideView(TreeNode root) { List res = new LinkedList(); if(root == null) return res; Queue queue = new LinkedList(); queue.add(root); //Perform BFS level by level while(queue.isEmpty() == false){ int size = queue.size(); for(int i = 0; i < size; i++){ TreeNode top = queue.remove(); //Check if current node is the last node in the current level if(i == size - 1){ res.add(top.val); } //Add the left if(top.left != null){ queue.add(top.left); } //Add the right if(top.right != null){ queue.add(top.right); } } } return res; } }

[@dkdlife6210]

Really nice solution using BFS.

[@easynow6599]

i did O(n) time and space and got 99.57% speed(if its accurate). I create a hashmap[level] = node.val so in the queue i keep the level also and put it in the hashmap but i do the node.right second (as in the video) so i keep the rightmost node. at the end i return hashmap.values()

[@minciNashu]

If you handle null case at the start of the function and return empty list, then inside your loop you can do res.append(q[-1].val) before the for loop and forego using that extra variable.

[@varunshrivastava2706]

I was able to clear 157 test cases out of 215, Its so frustrating when you are on the verge of solving a question completely on your own. I was also able to think of the solution to clear rest of the test cases but wasn't able to implement code for it!!!!

[@СтасюкАндрій]

Bro same thing is happening with me lol

[@СтасюкАндрій]

My solution is getting more and more complicated until I am finally done and I watch neetcode solution

[@varunshrivastava2706]

@@СтасюкАндрій Keep ur head up champ. Atleast you are trying which matters a lot. Just don't give up.

[@ladydimitrescu1155]

drawing the tree and pointing the fact that we have to look at the right most node made the solution so much easier

[@ChicoTheQue]

Can someone explain how the rightSide left nodes get overwritten by the right ones? How do the rightSide = node equal to the right node.

[@nuke4496]

took me awhile but here is the answer. the left node gets overwritten with the right node because the rightside variable is updated within the for loop

[@AhmedEbrahim-g2e]

Thanks for the question, thanks for the answer

[@premthapa9959]

based on leftmost depthmost : def f(node,ref,count = 0): if node==None:return None ref[count]=node.val f(node.left,ref,count+1) f(node.right,ref,count+1) ref = {} f(root,ref) return [ref[i] for i in ref.keys()] And dats it

[@sidazhong2019]

This problem is just slightly different than the standard BFS tree traversal. queue=[root] rs=[] while queue: for k in range(len(queue)): curr=queue.pop(0) if curr: rs.append(curr.val) #=============lol==========# queue.append(curr.left) queue.append(curr.right) return rs

[@The6thProgrammer]

If the question were better worded it would be easier. It took a bit to understand what was a valid "right side view" node. If it were instead worded as "return a list of the rightmost node at every level of the tree" it would have clicked much sooner for me.

[@TypicalRussianGuy]

Man, I really hate those "percentages" on the leetcode. Why can't they also show the "tiers" of the solution based on the time it took to solve it? I mean, for example, whether your solution is slow, medium, or fast. These "percentages" are deceving and may make one think their solution is bad when it's good and vice versa. It's kinda misleading.

[@danielsun716]

def rightSideView(self, root: Optional[TreeNode]) -> List[int]: # self if not root: return [] output = [] q = deque() q.append(root) while q: qLen = len(q) output.append(q[-1].val) for i in range(qLen): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return output

[@tylercarol-ci1yq]

hello sir so i study this question inside out outside by today i will be solving "left side of tree"... so do i write program upside down??

[@arunpranavat]

Thank you so much for this video.

[@dineshjmsbw25]

The more Intuitive way would be : For each level we will add right children first and then left. So that front of queue always pointing to right most node for that level.

[@minciNashu]

what difference does that make ? q[0] vs q[-1] ?

[@mastermax7777]

you should have explained better how rightSide left nodes get overwritten by the right ones, but other than that, good tutorial

[@ChicoTheQue]

@mastermax7777 can you explain this to me?

[@anjaliyadav9360]

Your explanations are the best!

[@cscsun3796]

The solution is so great. But I am pretty sure that I can never do it like this by myself at any given interview

[@subfytispot4279]

In the for loop check if i == 0 then append, the logic will be reduced

[@NikolayMishin]

thank you for good english!

[@sistaseetaram9008]

What is the time complexity? O(n)?

[@炒粿条-b1d]

I think so

[@whonayem01]

Great Solution! Thanks!

[@geuis]

Really couldn't get your algorithm to make sense, especially since you call out inserting the left node first several times. But you're assigning the left most node in the queue to rightSide. I tried this out myself and always get the left side nodes instead.

[@vallabhahere1564]

Great Video,Tnx!!

[@brainstormbalaclava5384]

runtime: faster that 0,01% submissions neetcode: it's a pretty efficient solution🤣

[@Emorinken]

Thank you very much

[@shilashm5691]

python easier solution res = [ ] if not root : return res queue = [ root ] while queue : for n in range(len(queue)) : first_val = queue.pop(0) if n == 0 : res.append(first_val.val) if first_val.right : queue.append(first_val.right) if first_val.left : queue.append(first_val.left) return res Just do the breadth first search, but start from the right side of the tree, and just get the first value from the queue. Thank me later.

[@flvyu]

Thank you!

[@adminweekend7518]

this is genius

[@RobinSingh-ms3zt]

Awesome solution

[@IK-xk7ex]

I could solve the problem by myself!

[@IK-xk7ex]

But anyway watched your @NeetCode video to check are there any better solution which I imagined

[@RahulJain-ye4gz]

""" 1 / \ 2 3 / \ \ 4 5 6 Initialization res = [] (to store the right side view) q = deque([1]) (initial queue containing the root node) Level 1 rightSide = None qLen = len(q) = 1 Process the level: node = q.popleft() (pops 1 from the queue) rightSide = 1 Add children of 1 to the queue: q.append(2), q.append(3) rightSide is 1, so res.append(1): res = [1] Queue now contains: [2, 3] Level 2 rightSide = None qLen = len(q) = 2 Process the level: node = q.popleft() (pops 2 from the queue) rightSide = 2 Add children of 2 to the queue: q.append(4), q.append(5) node = q.popleft() (pops 3 from the queue) rightSide = 3 Add children of 3 to the queue: q.append(None), q.append(6) rightSide is 3, so res.append(3): res = [1, 3] Queue now contains: [4, 5, None, 6] Level 3 rightSide = None qLen = len(q) = 4 Process the level: node = q.popleft() (pops 4 from the queue) rightSide = 4 No children to add to the queue node = q.popleft() (pops 5 from the queue) rightSide = 5 No children to add to the queue node = q.popleft() (pops None from the queue) Skip since node is None node = q.popleft() (pops 6 from the queue) rightSide = 6 No children to add to the queue rightSide is 6, so res.append(6): res = [1, 3, 6] Queue is now empty, so we exit the while loop Result The final right side view of the binary tree is [1, 3, 6].

[@Jbuckkz]

no need to have the for loop var rightSideView = function(root) { if (!root) return [] const queue = [[root,0]]; const result = []; while (queue.length) { const [node,i] = queue.shift(); result[i] = node?.val; if (node?.left) { queue.push([node.left, i + 1]); } if (node?.right) { queue.push([node.right, i + 1]) } } return result; };

[@KyuriousBot]

How can this be done using DFS?

[@asdfasyakitori8514]

Thanks!

[@NeetCode]

Thank you so much!

[@mk-19memelauncher65]

Raalizing this requires bfs and not dfs is 95% of the challenge

[@brokecoder]

If it's children is not null, I am going to take it's children - Neetcode

[@chrisy.703]

this illustration NOT matches the code at all...., but either one is great!

[@АльбусДамблодр]

yo, bro, there is actually a better solution! using bfs you can each level just add to a res q[-1] node

[@판다야키]

I get Time Limit Exceeded.. is it just me?

[@mrshreehari]

GOAT!

[@torvasdh]

This might be the most poorly written question on leetcode tf??

[@villurikishore7779]

This is the best solution I've seen and very crisp explanation.

[@Arizala213]

Thanks!

[@NeetCode]

Thank you so much!