# 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 = rightclass 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.

--

--