Problem statement
- Assuming you are viewing the tree from right side, what all notes will you see?
- Q. What can be the max number of nodes in the Tree?
Intuition
- There are three types of traversals available,preorder_traversalpostorder_traversal andinorder_traversal , inpreorder_traversal we go to the leftmost side before going to the right side, if from that we just remove the code to go to left, will that solve the problem.
- The problem statement is vague on Leetcode, it is not telling if right node is not there then will it show the left node behind it. Yes, if the right node is present then it will show the left node. This is the path which should be printed in that case,
- Do we need Level order traversal- Binary Tree traversal here?
- There are two loops while and nested for loop.
- Do Level order traversal- Binary Tree and create the levels array.
- Print the last element of the array.
- approach_should_be_mentioned_first
- dry_run_is_important
- edge_cases_are_important
Code
from collections import deque
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: TreeNode):
if root is None:
return None
queue = deque()
queue.append(root)
res = []
while queue:
temp = []
for _ in range(len(queue)):
node = queue.popleft()
temp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(temp)
ans = []
for lst in res:
ans.append(lst[-1])
return ans
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3, n1, n2)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6, n4)
n7 = TreeNode(7)
root = TreeNode(8, n3, n6)
sol = Solution()
ans = sol.rightSideView(root)
print(ans)ED- Right View of Binary Tree
⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠
Text Elements
8
1
3
6
2
4
5
Link to original
Attempt 1
Working: 
# Definition for a binary tree node.
'''
approach:
do level order traversal of tree and then print the last element
how do level order traversal happen?
use a queue, starting with root start pushing the element in queue,
pop the first element in queue and take its child and push them in the queue
keep proceeding till there is no element left,
do above with left and then right child
in initialization phase start queue with root element
create two arrays
in maintainance phase make temp variable as empty array after every iteration of first loop
in maintainance phase after every complete cycle of for loop push element in layer array
what happens in for loop?
in first iteration root needs to be pushed and left and root right need to be pushed and so on
Am in wrong in above?
Termination phase happens when queue gets null, when there is no left or right element queue gets null
dry run:
1 to 8
8
/ \
1 4
/ \
2 4
edge case? root null return null or empy list? []
first iteration:
8 is pushed in queue
8 poped and 1 and 4 pushed, len of q was 1 at starting so loop exits and temp added to layers
second iterations:
now length of q is 2 so for loop two iterations
1 is poped and 2 and 4 are pushed
4 is poped and nothing is pushed
third iteration:
'''
from collections import deque
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
queue = deque()
queue.append(root)
layers = []
while queue:
temp = []
for _ in range(len(queue)):
node = queue.popleft()
temp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
layers.append(temp)
ans = []
for layer in layers:
ans.append(layer[-1])
return ans