Binary Tree Right Side View

To solve this problem, we can perform a level-order traversal (breadth-first search) on the tree and keep track of the last element at each level. We will then return these last elements as the right-side view of the binary tree.

Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 of the current level, add to result
                if i == level_size - 1:
                    result.append(node.val)To solve this problem, we can perform a level-order traversal (breadth-first search) on the tree and keep track of the last element at each level. We will then return these last elements as the right-side view of the binary tree.

Python code that demonstrates this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 of the current level, add to result
                if i == level_size - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result

Explanation:

Empty Tree Check: If the root is None, we return an empty list.
Initialize Variables: result is initialized to hold the right-side view. A queue is used to store the nodes at the current level of traversal.
Breadth-First Traversal: Using a loop, we traverse each level of the tree. We determine the size of the current level and iterate over that many elements in the queue, processing each node and adding its children to the queue.
Add Right-Side Node: For the last node of each level (i.e., i == level_size - 1), we append its value to the result.
Process Children: If a node has a left or right child, we add them to the queue for processing in the next level.

The final result list will contain the values of the nodes that can be seen from the right side of the tree.

The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree, and the space complexity is (O(n)) as well, due to the use of the queue to store nodes at the current level of traversal.

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result

Explanation:

Empty Tree Check: If the root is None, we return an empty list.
Initialize Variables: result is initialized to hold the right-side view. A queue is used to store the nodes at the current level of traversal.
Breadth-First Traversal: Using a loop, we traverse each level of the tree. We determine the size of the current level and iterate over that many elements in the queue, processing each node and adding its children to the queue.
Add Right-Side Node: For the last node of each level (i.e., i == level_size - 1), we append its value to the result.
Process Children: If a node has a left or right child, we add them to the queue for processing in the next level.

The final result list will contain the values of the nodes that can be seen from the right side of the tree.