OVERVIEW BFS, Recursive DFS with Example : Binary Tree Right Side View — Hackerrank In Top 30 MAANG question-SQL
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?
- 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.
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:
