# Simple python BFS solution

• For a tree looks like:

``````    1
/    \
2       3
\
4
``````

We can use BFS to convert it as:

``````level 1: 1
level 2: 2 3
level 3: 4
``````

Then the output is the last node on each level (1,3,4).

Time complexity: O(N) we go through each node exactly once;
que.popleft() O(1)
que.append() O(1)

Space complexity: O(N) we use a 2-D array to store all nodes and use a deque for BFS,

where N is the size of tree.

``````  def rightSideView(self, root):
if not root: return []

que = collections.deque()
que.append((root, 0))
level_tree = []

while que:
node, level = que.popleft()

if len(level_tree) <= level:
level_tree.append([]) # new level
level_tree[level].append(node.val)

if node.left:
que.append((node.left, level + 1))
if node.right:
que.append((node.right, level + 1))

visible_nodes = []
for level_nodes in level_tree:
if level_nodes:
visible_nodes.append(level_nodes[-1])

return visible_nodes``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.