Skip to main content

Binary Tree Right Side View Solution

Problem Description​

Given the root of 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.

Examples​

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints​

  • The number of nodes in the tree is in the range [0, 100].
  • −100<=-100 <= Node.val <=100<= 100

Solution for Binary Tree Right Side View Problem​

Intuition​

The intuition behind the solution is to perform a level-order traversal (BFS) of the binary tree and record the value of the last node at each level, which represents the view from the right side.

Approach​

  1. Initialize an empty result list to store the right side view of the tree.
  2. Perform a level-order traversal (BFS) of the tree.
  3. At each level, record the value of the last node in the result list.
  4. Return the result list.

Code in Different Languages​

Written by @mahek0620

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):
result = []
if not root:
return result

queue = deque([root])

while queue:
level_length = len(queue)
for i in range(level_length):
node = queue.popleft()
if i == level_length - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return result

Complexity Analysis​

  • Time complexity: The time complexity of the solution is O(N)O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once during the level-order traversal.
  • Space complexity: The space complexity of the solution is O(N)O(N), where N is the number of nodes in the binary tree. This is because the space used by the queue for level-order traversal can be at most N in the worst case.

References​