Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Right View of a Binary Tree

Problem Statement

Given a root of the binary tree, return an array containing nodes in its right view.

The right view of a binary tree consists of nodes that are visible when the tree is viewed from the right side. For each level of the tree, the last node encountered in that level will be included in the right view.

Examples

Example 1

  • Input: root = [1, 2, 3, 4, 5, 6, 7]
  • Expected Output: [1, 3, 7]
  • Justification:
    • The last node at level 0 is 1.
    • The last node at level 1 is 3.
    • The last node at level 2 is 7.

.....

.....

.....

Like the course? Get enrolled and start learning!
Ali Simsek

Ali Simsek

· a year ago

for the input [1,2,3,4,5,6,7] expected output should be [1,3,7] as it's given in the example but when run the test cases, expected output seems that [1,3,5] which is wrong.

Show 1 reply
V

vipulmeh23

· 2 years ago

After the for loop iterates through the length of the level, just add the node that you get after popleft. Extra logic, does not make much sense.

from collections import deque

#class TreeNode:
#  def __init__(self, val):
#    self.val = val
#    self.left, self.right = None, None

class Solution:
  def traverse(self, root):
    result = [] # List[int]
    if root is None:
      return result

    # TODO: Write your code here
    q = deque()
    q.append(root)
    while q:
      level_size = len(q)
      for _ in range(level_size):
        node = q.popleft()
        
        if node.left:
          q.append(node.left)
        if node.right:
          q.append(node.right)
        
      result.append(node.val)

    return result