Nerd For Tech
Published in

Nerd For Tech

Binary Tree Right Side View — Day 73(Python)

Photo by Fabrice Villard on Unsplash

Today’s question is from Leetcode’s daily coding challenge February edition. This question is frequently asked among Facebook interviewers. Let us look into the problem statement.

199. Binary Tree Right Side View

Given 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:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---

The question wants us to print the right side view of the given input tree. The output should be ordered from top to bottom.

We can use level order traversal to traverse through the tree and then print the answer. Let us see how we can use level order traversal here.

Let us take an example,

Tree

Let us perform the level order traversal.

Level 1:

Level 2:

Level 3:

Level 4:

Answer:

What do we observe? We see that when we are traversing using level order, we need to take the last node from each level. These nodes will be our answer.

Since we have used level order traversal before, we would not be reiterating the algorithm. If you need a refresher, you can follow this link.

Let us look into the code snippet.

class RightSideFinder:
def rightSideView(self, root: TreeNode) -> List[int]:
queue = []
next_nodes = []
output = []
if root != None:
output = [root.val]
queue = [root]
while queue:
out = queue.pop(0)
if out.left:
next_nodes.append(out.left)
if out.right:
next_nodes.append(out.right)
if queue == []:
if next_nodes != []:
output.append(next_nodes[-1].val)
queue, next_nodes = next_nodes, queue
return output
else:
return []

Complexity analysis.

Time Complexity

We are visiting each node once, hence the time complexity is O(N) where N is the number of nodes.

Space Complexity.

We are visiting each node once and storing it in the queue. In the worst case, if all the children are in the same x level, we might have to hold all the nodes in the queue, hence the space complexity is O(N) where N is the number of nodes.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store