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

แชร์
ฝัง
  • เผยแพร่เมื่อ 23 พ.ย. 2024

ความคิดเห็น • 91

  • @NeetCode
    @NeetCode  3 ปีที่แล้ว +6

    Tree Question Playlist: th-cam.com/video/OnSn2XEQ4MY/w-d-xo.html

    • @littlebox4328
      @littlebox4328 3 ปีที่แล้ว

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

  • @rathnashakthi5012
    @rathnashakthi5012 3 ปีที่แล้ว +55

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

  • @rkwong792music
    @rkwong792music 2 ปีที่แล้ว +40

    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
      @DmitriyKl ปีที่แล้ว +4

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

    • @hwang1607
      @hwang1607 11 หลายเดือนก่อน +2

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

    • @syafzal273
      @syafzal273 10 หลายเดือนก่อน

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

  • @ancientgearsynchro
    @ancientgearsynchro 7 หลายเดือนก่อน +3

    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
    @swaroopacharjee2767 2 ปีที่แล้ว +10

    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
      @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
      @erickmercado1711 8 หลายเดือนก่อน

      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
      @erickmercado1711 8 หลายเดือนก่อน

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

  • @thelookofdisapproval8234
    @thelookofdisapproval8234 3 ปีที่แล้ว +14

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

  • @camoenv3272
    @camoenv3272 2 ปีที่แล้ว +25

    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)

  • @stephentomaszewski8501
    @stephentomaszewski8501 ปีที่แล้ว +6

    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
      @bigboimoe 7 หลายเดือนก่อน +1

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

  • @mohamadilhamramadhan6354
    @mohamadilhamramadhan6354 ปีที่แล้ว +3

    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
    @Cloud-577 2 ปีที่แล้ว +8

    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
      @kuoyulu6714 ปีที่แล้ว +1

      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
    @FirePizza94 2 ปีที่แล้ว +3

    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
      @shatakshisharma8557 3 หลายเดือนก่อน

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

  • @romo119
    @romo119 ปีที่แล้ว +2

    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
      @The6thProgrammer ปีที่แล้ว +1

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

  • @Japakak
    @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
    @darr915 ปีที่แล้ว +2

    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.

  • @villurikishore7779
    @villurikishore7779 2 ปีที่แล้ว

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

  • @gulshankumar17
    @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
    @numberonep5404 2 ปีที่แล้ว +1

    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_
    @SAVAGE_AF_ ปีที่แล้ว

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

  • @sebselassie
    @sebselassie 9 หลายเดือนก่อน

    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_
    @_control_ 2 ปีที่แล้ว +1

    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
    @chingiskhant4971 4 หลายเดือนก่อน

    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
    @EricProgramming 3 ปีที่แล้ว +6

    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
      @dkdlife6210 2 ปีที่แล้ว

      Really nice solution using BFS.

  • @easynow6599
    @easynow6599 2 ปีที่แล้ว +1

    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
    @minciNashu 2 ปีที่แล้ว +1

    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
    @varunshrivastava2706 2 ปีที่แล้ว +2

    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
      @varunshrivastava2706 ปีที่แล้ว

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

  • @ladydimitrescu1155
    @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
    @ChicoTheQue ปีที่แล้ว +3

    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
      @nuke4496 4 หลายเดือนก่อน +1

      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
      @AhmedEbrahim-g2e 22 วันที่ผ่านมา

      Thanks for the question, thanks for the answer

  • @premthapa9959
    @premthapa9959 2 ปีที่แล้ว

    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
    @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
    @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
    @TypicalRussianGuy ปีที่แล้ว +1

    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
    @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
    @tylercarol-ci1yq 3 หลายเดือนก่อน

    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
    @arunpranavat 3 หลายเดือนก่อน

    Thank you so much for this video.

  • @dineshjmsbw25
    @dineshjmsbw25 2 ปีที่แล้ว

    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
      @minciNashu 2 ปีที่แล้ว

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

  • @mastermax7777
    @mastermax7777 ปีที่แล้ว +1

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

    • @ChicoTheQue
      @ChicoTheQue ปีที่แล้ว

      @mastermax7777 can you explain this to me?

  • @anjaliyadav9360
    @anjaliyadav9360 2 ปีที่แล้ว

    Your explanations are the best!

  • @cscsun3796
    @cscsun3796 9 หลายเดือนก่อน

    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
    @subfytispot4279 หลายเดือนก่อน

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

  • @NikolayMishin
    @NikolayMishin ปีที่แล้ว

    thank you for good english!

  • @sistaseetaram9008
    @sistaseetaram9008 3 ปีที่แล้ว +3

    What is the time complexity? O(n)?

  • @whonayem01
    @whonayem01 2 ปีที่แล้ว

    Great Solution! Thanks!

  • @geuis
    @geuis 5 หลายเดือนก่อน

    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
    @vallabhahere1564 ปีที่แล้ว

    Great Video,Tnx!!

  • @brainstormbalaclava5384
    @brainstormbalaclava5384 8 หลายเดือนก่อน

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

  • @Emorinken
    @Emorinken หลายเดือนก่อน

    Thank you very much

  • @shilashm5691
    @shilashm5691 2 ปีที่แล้ว +6

    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.

  • @RobinSingh-ms3zt
    @RobinSingh-ms3zt 2 ปีที่แล้ว

    Awesome solution

  • @IK-xk7ex
    @IK-xk7ex ปีที่แล้ว

    I could solve the problem by myself!

    • @IK-xk7ex
      @IK-xk7ex ปีที่แล้ว

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

  • @RahulJain-ye4gz
    @RahulJain-ye4gz 5 หลายเดือนก่อน

    """
    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
    @Jbuckkz 11 หลายเดือนก่อน

    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
    @KyuriousBot 2 ปีที่แล้ว

    How can this be done using DFS?

  • @asdfasyakitori8514
    @asdfasyakitori8514 2 ปีที่แล้ว +1

    Thanks!

    • @NeetCode
      @NeetCode  2 ปีที่แล้ว +1

      Thank you so much!

  • @mk-19memelauncher65
    @mk-19memelauncher65 10 หลายเดือนก่อน

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

  • @brokecoder
    @brokecoder ปีที่แล้ว

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

  • @chrisy.703
    @chrisy.703 4 หลายเดือนก่อน

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

  • @АльбусДамблодр
    @АльбусДамблодр 6 หลายเดือนก่อน

    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
    @mrshreehari 2 ปีที่แล้ว

    GOAT!

  • @torvasdh
    @torvasdh 10 หลายเดือนก่อน +1

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

  • @villurikishore7779
    @villurikishore7779 2 ปีที่แล้ว

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

  • @Arizala213
    @Arizala213 2 ปีที่แล้ว +2

    Thanks!

    • @NeetCode
      @NeetCode  2 ปีที่แล้ว +2

      Thank you so much!