Search⌘ K
Home
Courses
Decode the Coding Interview in Python: Real-World Examples

Binary Tree Right Side View

Explore how to obtain the right side view of a binary tree using depth-first search. Understand the process of recursively traversing from right to left at each level, and learn to return the visible nodes as an array. This lesson covers time and space complexities, helping you apply this approach in coding interviews effectively.

We'll cover the following...

Description

You are given a binary tree T. Imagine you are standing to the right of it; you have to return the value of the nodes you can see from top to bottom.

You have to return the rightmost nodes on their respective levels in the form of an array.

Let’s discuss an example below:

Coding exercise

Python 3.5
from TreeNode import *
def right_side_view(root):
  # write your code here
  pass
Binary tree right side view

Solution

We can use a depth-first search (DFS) to solve this problem. The intuition here is to traverse the tree level by level recursively, starting from the rightmost node for each recursive call.

Let’s review the implementation below:

Python 3.5
from TreeNode import *
def right_side_view(root):
  if root is None:
      return []
  rightside = []
  
  def DFS(node: TreeNode, level: int) -> None:
      if level == len(rightside):
          rightside.append(node.val)
      for child in [node.right, node.left]:
          if child:
              DFS(child, level + 1)
          
  DFS(root, 0)
  return rightside
# Driver Code
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4);
root.left.right = TreeNode(5);
root.right.left = TreeNode(6);
root.right.right = TreeNode(7);
root.right.right.left = TreeNode(8);
print(right_side_view(root))
Binary tree right side view

Complexity measures

Time Complexity
...