OVERVIEW BFS, Recursive DFS with Example : Binary Tree Right Side View

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---

Which approach to choose, BFS or DFS?

  • The problem is to return a list of last elements from all levels, so it’s the way more natural to implement BFS here.
  • Time complexity is the same O(N) both for DFS and BFS since one has to visit all nodes.
  • Space complexity is O(H) for DFS and
    O(D) for BFS, where HH is a tree height, and D is a tree diameter. They both result in O(N) space in the worst-case scenarios: skewed tree for DFS and complete tree for BFS.
  • Pop-out a node from the left.
  • Push the left child into the queue, and then push the right child.

Approach 3: BFS: One Queue + Level Size Measurements

Instead of using the sentinel, we could write down the length of the current level.

# Definition for a binary tree node.
# class TreeNode:
# 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) -> List[int]:

# bfs and the rightmost node
# iterative with queue
if not root:
return []
q = collections.deque()
q.append(root)

res = []

while q:

length = len(q)

for _ in range(length):
node = q.popleft()

if node.left : q.append(node.left)
if node.right : q.append(node.right)

res.append(node.val)

return res
  • Space complexity: O(D) to keep the queues, where D is a tree diameter. Let’s use the last level to estimate the queue size. This level could contain up to N/2 tree nodes in the case of complete binary tree.

Approach 4: Recursive DFS

Everyone likes recursive DFS, so let’s add it here as well. The idea is simple: to traverse the tree level by level, starting each time from the rightmost child.

class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if root is None:
return []

rightside = []

def helper(node: TreeNode, level: int) -> None:
if level == len(rightside):
rightside.append(node.val)
for child in [node.right, node.left]:
if child:
helper(child, level + 1)

helper(root, 0)
return rightside
  • Space complexity: O(H) to keep the recursion stack, where H is a tree height. The worst-case situation is a skewed tree, when H=N.
  1. Boundary of Binary Tree

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store