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

Medium : https://leetcode.com/problems/binary-tree-right-side-view/

Given 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.

**Example:**

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

/ \

2 3 <---

\ \

5 4 <---

**Solution**

**DFS vs. BFS**

There are two ways to traverse the tree: DFS *depth first search* and BFS *breadth first search*. Here is a small summary

BFS traverses level by level, and DFS first goes to the leaves.

*Which approach to choose, BFS or DFS?*

*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 H*H*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.

BFS wins for this problem, so let’s use the opportunity to check out three different BFS implementations with the queue.

**BFS implementation**

All three implementations use the queue in a standard BFS way:

- Push the root into the queue.
- 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.

**Algorithm**

**Code**

# 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

**Complexity Analysis**

- Time complexity: O(N) since one has to visit each node.
- 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.

**TRICK : we traverse right first and then the left.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

**Complexity Analysis**

- Time complexity: O(N) since one has to visit each node.
- 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.

Runtime: 24 ms, faster than 96.75% of Python3 online submissions for Binary Tree Right Side View.

Memory Usage: 14.3 MB, less than 38.04% of Python3 online submissions for Binary Tree Right Side View.

**Next to try:**