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

0:00 - Read the problem
1:50 - Drawing Explanation
6:30 - Coding Explanation

leetcode 199

#breadth #first #python

[rkwongmusic]

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

[thelookofdisapproval]

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

[rathnashakthi]

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 YouTubers, but Yours is the BEST!! Thank you so much!! keep doing what you're doing.

[stephentomaszewski]

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.

[Cloud-]

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

[FirePizza]

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

[EricProgramming]

Easy Java Solution:

class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new LinkedList<>();
if(root == null) return res;
Queue<TreeNode> 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;
}
}

[romo]

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

[SAVAGE_AF_]

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

[villurikishore]

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

[numberonep]

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())

[chingiskhant]

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

[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.

[darr]

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.

[ladydimitrescu]

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

[tylercarol-ciyq]

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??

[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) <= level:
ans.append(node.val)
else:
ans[level] = node.val
level += 1
if node.left:
queue.append((node.left, level))
if node.right:
queue.append((node.right, level))
return ans

[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

[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.

[brainstormbalaclava]

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