Binary Tree Right Side View - Breadth First Search - Leetcode 199
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/binary-t...
0:00 - Read the problem
1:50 - Drawing Explanation
6:30 - Coding Explanation
leetcode 199
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#breadth #first #python - Věda a technologie
Tree Question Playlist: czcams.com/video/OnSn2XEQ4MY/video.html
Very good explaination thanks, do you mind to explain the dfs approach for this?
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 CZcamsrs, but Yours is the BEST!! Thank you so much!! keep doing what you're doing.
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
That's the solution I came up with. q[-val] to grab the rightmost node's value is the key here
i came up with this as well, definitely makes it easier if you've done the previous question
I came up with the same after doing level order and I think it is easier to read
I did this a while ago, using DFS. just keep track of current level, and largest level you encountered yet.
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
the dedication which you put in to create the videos is impressive! Please don't stop, ever! Thank you so much!
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.
That's what I had as well, much more readable code and intuitive answer that you can come up with during an interview.
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
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
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
Also you should use None instead of [ ] as it wont handle the None case correctly
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)
thanks pal
This is the best solution I've seen and very crisp explanation.
Your explanations are the best!
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.
Great Solution! Thanks!
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
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.
Great Video,Tnx!!
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
100% this is what I did as well. More intuitive
Awesome solution
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.
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;
}
}
Really nice solution using BFS.
drawing the tree and pointing the fact that we have to look at the right most node made the solution so much easier
thank you for good english!
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()
Thanks!
Thank you so much!
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.
me 2!
Can someone explain how the rightSide left nodes get overwritten by the right ones? How do the rightSide = node equal to the right node.
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
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())
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
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
@@user-lz5mb5nj2r Keep ur head up champ. Atleast you are trying which matters a lot. Just don't give up.
How can this be done using DFS?
runtime: faster that 0,01% submissions
neetcode: it's a pretty efficient solution🤣
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
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)
GOAT!
What is the time complexity? O(n)?
I think so
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
you should have explained better how rightSide left nodes get overwritten by the right ones, but other than that, good tutorial
@mastermax7777 can you explain this to me?
The solution is so great.
But I am pretty sure that I can never do it like this by myself at any given interview
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.
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.
what difference does that make ? q[0] vs q[-1] ?
I could solve the problem by myself!
But anyway watched your @NeetCode video to check are there any better solution which I imagined
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
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
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
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;
}
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
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.
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.
If it's children is not null, I am going to take it's children - Neetcode
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.
Thank you!
this is genius
"""
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].
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;
};
Raalizing this requires bfs and not dfs is 95% of the challenge
I get Time Limit Exceeded.. is it just me?
yo, bro, there is actually a better solution! using bfs you can each level just add to a res q[-1] node
this illustration NOT matches the code at all...., but either one is great!
This might be the most poorly written question on leetcode tf??
I just created a list of nodes and appended val of rightmost node on each level. Simple to write and did okay on the (not very meaningful) speed
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
results = []
if not root:
return results
this_level = [root]
next_level = [root]
while len(next_level) > 0:
next_level = []
results.append(this_level[-1].val)
for node in this_level:
if node.left: next_level.append(node.left)
if node.right: next_level.append(node.right)
this_level = next_level
return results
This is the best solution I've seen and very crisp explanation.
Thanks!
Thank you so much!