Binary Tree Right Side View
Problem
https://leetcode.com/problems/binary-tree-right-side-view/
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:
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
Pattern
Tree, Depth-First Search, Breadth-First Search, Binary Tree
Approaches
Explanation
The right side view of a binary tree can be obtained by performing a level-order traversal (BFS) of the tree. The last node of each level is the node that is visible from the right side. To implement this, we can use the queue based implementation of BFS, adding the left child before the right child to ensure that the rightmost node is processed last. We also add the level number with each node so that we know when we have moved to the next level, which is when the level number changes.
Code
from __future__ import annotations
from collections import deque
class TreeNode:
"""Node in a binary tree."""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
@classmethod
def from_list(cls, vals: list[int | None]) -> TreeNode | None:
if not vals:
return None
root = cls(vals[0])
queue = deque([root])
children = iter(vals[1:])
while queue:
node = queue.popleft()
for side in ("left", "right"):
val = next(children, None)
if val is not None:
child = cls(val)
setattr(node, side, child)
queue.append(child)
return root
def to_list(self) -> list:
result = []
queue = [self]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def rightSideView(root: TreeNode | None) -> list[int]:
"""Returns the right side view of a binary tree as a list of values."""
if root is None:
return []
view = []
queue = deque([(root, 0)])
while queue:
node, level = queue.popleft()
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
if len(queue) == 0 or level < queue[0][1]:
view.append(node.val)
return view
Test
>>> from binary_tree_right_side_view__bfs import rightSideView, TreeNode
>>> rightSideView(TreeNode.from_list([1, 2, 3, None, 5, None, 4]))
[1, 3, 4]
>>> rightSideView(TreeNode.from_list([1, None, 3]))
[1, 3]
>>> rightSideView(None)
[]
Complexity
\(n\) is the number of nodes in tree 1
Measure |
Complexity |
Notes |
|---|---|---|
Time |
\(O(n)\) |
visit each node once |
Auxiliary Space |
\(O(\log n)\) |
maximum number of nodes in the queue is the maximum width of the tree |