Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches
    Data Structures & Algorithms

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    codeanddebugBy codeanddebug2 September 2025No Comments4 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve right side View of Binary Tree
    Share
    Facebook Twitter LinkedIn Pinterest Email

    The Binary Tree Right Side View problem asks us to return the list of nodes that are visible when the tree is viewed from the right-hand side.

    In other words:

    • For every level in the binary tree, we need to find the rightmost node.
    • These rightmost nodes, from top to bottom, form the “right side view”.

    Here’s the [Problem Link] to begin with.


    Examples

    Example 1

    Input: [1,2,3,null,5,null,4]
    Output: [1,3,4]
    
    Explanation:
    Level 0 → Rightmost = 1
    Level 1 → Rightmost = 3
    Level 2 → Rightmost = 4

    Example 2

    Input: [1,null,3]
    Output: [1,3]

    Example 3

    Input: []
    Output: []

    Intuition

    The main task is to capture the last (rightmost) node at each depth/level.
    There are two natural ways to achieve this:

    1. Breadth-First Search (BFS) – Traverse level by level and pick the last node at each level.
    2. Depth-First Search (DFS) – Always visit right nodes before left nodes, and record the first node encountered at each depth.

    Both methods solve the problem efficiently, but they differ in how they traverse the tree.


    Solution 1: BFS (Level Order Traversal)

    Approach

    1. Perform a level-order traversal using a queue.
    2. At each level, process all nodes from left to right.
    3. The last node processed at that level is the one visible from the right.
    4. Append that node’s value to the result list.

    This ensures that for every level, the rightmost node is captured.


    BFS Code

    from collections import deque
    
    class Solution:
        def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
            if not root:
                return []
    
            result = []
            queue = deque([root])
    
            while queue:
                level_size = len(queue)
                for i in range(level_size):
                    node = queue.popleft()
    
                    # If it's the last node at this level, add it to result
                    if i == level_size - 1:
                        result.append(node.val)
    
                    # Push children into queue
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
    
            return result

    BFS Dry Run

    Tree: [1,2,3,null,5,null,4]

    • Level 0 → [1] → pick 1.
    • Level 1 → [2,3] → pick 3.
    • Level 2 → [5,4] → pick 4.

    Result = [1,3,4].


    BFS Complexity

    • Time Complexity: O(N) – each node is visited once.
    • Space Complexity: O(W) – where W is the maximum width of the tree (queue size).

    Solution 2: DFS (Right-First Traversal)

    Approach

    1. Perform a DFS traversal, starting from the root.
    2. Always visit the right child before the left child.
    3. Keep track of the current depth.
    4. If it’s the first time visiting this depth, record the node (since the rightmost node will be visited first).

    This guarantees that for each depth, the rightmost node is chosen.


    DFS Code

    class Solution:
        def dfs(self, node, depth, result):
            if not node:
                return
    
            # If this depth is being visited for the first time, add node
            if depth == len(result):
                result.append(node.val)
    
            # Visit right child first, then left child
            self.dfs(node.right, depth + 1, result)
            self.dfs(node.left, depth + 1, result)
    
        def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
            result = []
            self.dfs(root, 0, result)
            return result

    DFS Dry Run

    Tree: [1,2,3,null,5,null,4]

    • Start at root (depth 0) → record 1.
    • Go right to node 3 (depth 1) → record 3.
    • Go right again to node 4 (depth 2) → record 4.
    • Backtrack left → nodes at depths already recorded → ignore.

    Result = [1,3,4].


    DFS Complexity

    • Time Complexity: O(N) – each node is visited once.
    • Space Complexity: O(H) – where H = height of the tree (recursion stack).

    BFS vs DFS Comparison

    AspectBFS (Level Order)DFS (Right-First)
    TraversalLevel by level (queue)Depth by depth (recursion)
    OrderPick last node in each levelPick first node at each depth
    Space UsageO(W), where W = max widthO(H), where H = tree height
    ImplementationIterative (queue)Recursive (stack)

    Both are equally correct. BFS is often more intuitive, while DFS is elegant and shorter.


    Conclusion

    The Binary Tree Right Side View problem can be solved using:

    • BFS: Traverse level by level, pick the last node at each level.
    • DFS: Traverse right before left, record the first node at each depth.

    Both solutions run in O(N) time and provide the correct right-side view of the tree.

    For interview preparation, it’s useful to know both approaches since BFS is straightforward while DFS highlights recursive tree traversal skills.


    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Binary Trees Medium
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleBottom View of Binary Tree | BFS with Horizontal Distance Mapping
    Next Article Symmetric Tree | Leetcode 101 | Recursive DFS Approach
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    2 September 2025
    Data Structures & Algorithms

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025
    Data Structures & Algorithms

    Top View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (240)
      • Beginner (82)
      • Expert (52)
      • Intermediate (106)
    • Uncategorised (1)
    Recent Posts

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    2 September 2025

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    2 September 2025

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Top View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Vertical Order Traversal of a Binary Tree | Leetcode 987 | BFS + Sorting Solution

    2 September 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.