Binary Tree Right Side View — Day 73(Python)
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.
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,
Let us perform the level order traversal.
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.
def rightSideView(self, root: TreeNode) -> List[int]:
queue = 
next_nodes = 
output = 
if root != None:
output = [root.val]
queue = [root]
out = queue.pop(0)
if queue == :
if next_nodes != :
queue, next_nodes = next_nodes, queue
We are visiting each node once, hence the time complexity is O(N) where N is the number of nodes.
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.