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:

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

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.

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:

  1. Populating Next Right Pointers in Each Node
  2. Boundary of Binary Tree

Currently preparing for interviews

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