Problem: Leetcode 199 – Binary Tree Right Side View
Description:
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
1 <--- (visible from the right)
/ \
2 3 <--- (3 is visible from the right)
\ \
5 4 <--- (4 is visible from the right)Example 2:
Input: root = [1,null,3]
Output: [1,3]Example 3:
Input: root = []
Output: []Analysis:
The task is to return the values of nodes visible from the right side of the tree, starting from the root. To solve this, we can use a level-order traversal (breadth-first search) and, at each level, record the last node encountered (which would be the rightmost node in that level).
We can achieve this by performing a BFS using a queue and, at each level of the tree, noting down the rightmost node (i.e., the last node at each depth level).
Python Code:
from collections import deque
def rightSideView(root):
if not root:
return []
q = deque([root]) # Queue for BFS
res = [] # List to store the right-side view nodes
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
# If it's the last node in the current level, add it to the result
if i == level_size - 1:
res.append(node.val)
# Add left and right children if they exist
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return resExample Usage:
# Example Tree: [1, 2, 3, null, 5, null, 4]
# Create the binary tree and use the rightSideView function
# Output: [1, 3, 4]Time Complexity:
The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because we perform a breadth-first search and visit each node exactly once.