Binary Tree Right Side View

Binary Tree Right Side View

Problem Description: Given the root node of a binary tree, return the node values visible from the right side of the tree, ordered from top to bottom. In other words, return the value of the rightmost node at each level.

Solution Approach: This problem is essentially a variation of the level-order traversal of a binary tree. In standard level-order traversal, we visit each node level by level. To obtain the right side view, we only need to record the value of the last node (i.e., the rightmost node) at each level during traversal. This can be achieved using either Breadth-First Search (BFS) or Depth-First Search (DFS) strategies.

Method One: Breadth-First Search (BFS) - Using a Queue

BFS is the most intuitive method for solving this problem. We use a queue to assist with level-order traversal.

Initialization: If the root node is empty, return an empty list immediately. Otherwise, enqueue the root node.
Process Each Level in a Loop: As long as the queue is not empty, there are unprocessed levels.
a. Record the number of nodes in the current level: Before processing the current level, first obtain the current length of the queue, levelSize. This length is the number of nodes in the current level.
b. Traverse all nodes in the current level: Use a loop to dequeue levelSize nodes from the queue.
- For each dequeued node, first check its left and right child nodes. If they are not empty, enqueue them in order (left then right) to prepare for the traversal of the next level.
- Key point: When we traverse to the last node of the current level (i.e., when the loop variable i equals levelSize - 1), this node is the one visible from the right side. We add this node's value to the result list.
Return the Result: When the queue is empty and all levels have been processed, return the result list.

Illustrative Process (using the binary tree [1,2,3,null,5,null,4] as an example):

    1        <-- Level 0
   / \
  2   3      <-- Level 1
   \   \
    5   4    <-- Level 2

Initialization: queue = [1], result list = []
Process Level 0: levelSize = 1
- Dequeue node 1. i=0 is the last node, add value 1 to result. Enqueue its left and right children 2 and 3.
- Result list = [1], queue = [2, 3]
Process Level 1: levelSize = 2
- Dequeue node 2 (i=0). It is not the last node, do not record. Enqueue its right child 5.
- Queue = [3, 5]
- Dequeue node 3 (i=1, is the last node). Add value 3 to result. Enqueue its right child 4.
- Result list = [1, 3], queue = [5, 4]
Process Level 2: levelSize = 2
- Dequeue node 5 (i=0, is it the last node? No, there are two nodes in this level). It is not the last node, do not record. It has no children.
- Queue = [4]
- Dequeue node 4 (i=1, is the last node). Add value 4 to result. It has no children.
- Result list = [1, 3, 4], queue = []
Queue is empty, return result [1, 3, 4].

Code Implementation (Python):

from collections import deque
# 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]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            # Traverse all nodes in the current level
            for i in range(level_size):
                node = queue.popleft()
                # If it's the last node of the current level, add to result
                if i == level_size - 1:
                    result.append(node.val)
                # Enqueue left and right children for the next level
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
        return result

Method Two: Depth-First Search (DFS) - Recursion

The DFS method adopts a different approach: we traverse in the order root node -> right subtree -> left subtree (this ensures we always visit the rightmost node first at each level), while recording the current node's depth.

Recursive Function Design: Define a recursive function dfs(node, depth).
- node: The node currently being visited.
- depth: The depth of the current node (root node depth is 0).
Recursive Process:
- If the current node is empty, return directly.
- Key Check: If the current depth depth equals the length of the result list result, it means we are reaching this depth for the first time. Since we recursively call the right subtree first, this "first arrival" node must be the rightmost node at that depth. Therefore, add the current node's value to the result list.
- Then, first recursively call the right child node (depth + 1), followed by the left child node (depth + 1).
Initiate Recursion: Start the recursion from the root node and depth 0.

Illustrative Process (using the same tree [1,2,3,null,5,null,4] as an example):

Call dfs(1, 0):
- depth=0, result length=0, equal. Add 1 to result. result = [1]
- First recurse on right subtree: dfs(3, 1)
  - depth=1, result length=1, equal. Add 3 to result. result = [1, 3]
  - First recurse on right subtree: dfs(4, 2)
    - depth=2, result length=2, equal. Add 4 to result. result = [1, 3, 4]
    - Recurse on left subtree (empty, return)
  - Then recurse on left subtree (empty, return)
- Then recurse on left subtree: dfs(2, 1)
  - depth=1, result length=2, not equal (meaning depth 1 already has node 3), do not add to result.
  - First recurse on right subtree: dfs(5, 2)
    - depth=2, result length=3, not equal (meaning depth 2 already has node 4), do not add to result.
  - Then recurse on left subtree (empty, return)
Return result [1, 3, 4].

Code Implementation (Python):

# 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]:
        result = []
        
        def dfs(node, depth):
            if not node:
                return
            # If current depth equals the result list length, it's the first time at this depth, current node is the rightmost
            if depth == len(result):
                result.append(node.val)
            # Right first, then left, ensures visiting the rightmost node first at each level
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        dfs(root, 0)
        return result

Summary:

BFS Method: Clear logic, easy to understand. Performs level-order traversal via a queue, recording the last node of each level.
DFS Method: Concise code. Leverages recursion order (right then left) and depth information to cleverly ensure the first node visited at each level is the rightmost one.
Both methods have time and space complexity of O(N), where N is the number of nodes in the tree. In actual interviews, mastering one method is sufficient, though explaining both approaches is even better.