#199

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Right Side View

The Binary Tree Right Side View problem asks you to return the visible nodes from the right side of a binary tree, traversed from top to bottom.

tree depth first search breadth first search binary tree

Problem Statement

You are given the root of a binary tree. Imagine standing on the right side of the tree, and you must return the values of the nodes visible when viewed from the right side. The nodes should be listed in top-to-bottom order.

For example, given the tree [1,2,3,null,5,null,4], the nodes visible from the right side are [1,3,4]. The tree's right side view captures the last node of each row as traversed from the top down, using a level order or depth-first approach.

Examples

Example 1

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Example 2

Input: root = [1,2,3,4,null,null,null,5]

Output: [1,3,4,5]

Example 3

Input: root = [1,null,3]

Output: [1,3]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution Approach

Breadth-First Search (BFS)

BFS explores the tree level by level, capturing the last node seen at each level. Traverse the tree using a queue, and for each level, keep track of the rightmost node.

Depth-First Search (DFS)

DFS can be employed by visiting the right subtree first, ensuring that the rightmost nodes are encountered before their left counterparts. Track the depth to ensure that you add the first node for each level.

State Tracking

In both BFS and DFS, use state tracking to monitor which level nodes have been seen. For BFS, this is naturally managed by the queue, while for DFS, a depth tracker helps ensure only the first node per level is included.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of nodes in the tree, as each node is visited once. The space complexity for BFS is O(n) due to the queue, and for DFS, it is O(h), where h is the height of the tree due to the recursion stack.

What Interviewers Usually Probe

Can the candidate explain the difference in approach between BFS and DFS for this problem?
Does the candidate understand the importance of tracking the rightmost nodes?
Does the candidate optimize space by choosing the appropriate traversal strategy for the tree's shape?

Common Pitfalls or Variants

Common pitfalls

Confusing the BFS and DFS traversal methods or not choosing the optimal one for the problem's constraints.
Failing to account for the edge case of an empty tree or ensuring the correct handling of null nodes.
Incorrectly managing the state during traversal, leading to missing or extra nodes in the output.

Follow-up variants

What if the tree is extremely unbalanced? Can you still solve it efficiently?
How does the solution change if you need to return the left side view instead of the right?
Can you solve the problem without using recursion?

FAQ

What is the key difference between BFS and DFS in solving the Binary Tree Right Side View problem?

BFS processes nodes level by level, ensuring the last node at each level is captured, while DFS explores the tree depth-first, preferring right-side nodes.

How do I handle null nodes or missing children in the Binary Tree Right Side View?

Ensure you handle null nodes appropriately by checking for them in your traversal process. In BFS, these are naturally skipped; in DFS, ensure recursion handles them correctly.

Can I solve the Binary Tree Right Side View problem with just an iterative DFS?

Yes, an iterative DFS can be used, typically with a stack, by tracking the depth and ensuring you only capture the rightmost node at each level.

How does the tree's shape impact the solution to the Binary Tree Right Side View?

The tree's shape affects the space complexity of DFS and BFS. A more unbalanced tree will impact DFS's stack depth, while BFS requires more space to handle a wide tree.

What is the optimal way to solve the Binary Tree Right Side View if the tree is very large?

For large trees, an optimal solution would likely involve BFS to minimize recursion stack depth and avoid performance issues in unbalanced trees.

terminal

Solution

Solution 1: BFS

We can use breadth-first search (BFS) and define a queue $\textit{q}$ to store the nodes. We start by putting the root node into the queue. Each time, we take out all the nodes of the current level from the queue. For the current node, we first check if the right subtree exists; if it does, we put the right subtree into the queue. Then, we check if the left subtree exists; if it does, we put the left subtree into the queue. This way, the first node taken out from the queue each time is the rightmost node of that level.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        while q:
            ans.append(q[0].val)
            for _ in range(len(q)):
                node = q.popleft()
                if node.right:
                    q.append(node.right)
                if node.left:
                    q.append(node.left)
        return ans

Solution 2: DFS

Use DFS (depth-first search) to traverse the binary tree. Each time, traverse the right subtree first, then the left subtree. This way, the first node visited at each level is the rightmost node of that level.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        while q:
            ans.append(q[0].val)
            for _ in range(len(q)):
                node = q.popleft()
                if node.right:
                    q.append(node.right)
                if node.left:
                    q.append(node.left)
        return ans

Continue Practicing

#226 invert binary tree #117 populating next right pointers in each node ii #116 populating next right pointers in each node