Binary Tree Right Side View

Patrick Leaton
Published: July 23, 2021, 6:05 p.m.
Problem Description

Given the root of 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 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

 

The description was taken from https://leetcode.com/problems/binary-tree-right-side-view/.

Problem Solution

# Iterative BFS
# O(N) Time, O(Width) Space
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return root
        output = []
 
        def bfs(root:TreeNode) -> None:
            queue = collections.deque([root])
            while queue:
                right_most = None
                level_width = len(queue)
                for _ in range(level_width):
                    node = queue.popleft()
                    right_most = node
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                if right_most:
                    output.append(right_most.val)
        bfs(root)
        return output
 
# Recursive DFS
# O(N) Time, O(Depth) Space
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return root
        output = []
       
        def dfs(node: TreeNode, level: int) -> None:
            if not root:
                return 
            if level == len(output):
                output.append(node.val)
            if node.right:
                dfs(node.right, level + 1)
            if node.left:
                dfs(node.left, level + 1)
               
        dfs(root, 0)
        return output
 

Problem Explanation

Iterative Breadth-First Search

Let's start with a more straightforward solution, the iterative one.

We can do a traditional BFS but we will set a right_most pointer to each node we process within a given level.  By doing this, the last node seen in each level will be the one farthest on the right side. 

First off, if there is no root that was input, we have nothing to see on the right side so we are done.

        if not root:
            return root

 

Otherwise, we will start by initializing our output array.

        output = []

Next, we will create our bfs function.

        def bfs(root:TreeNode) -> None:

 

We'll initialize a queue from a deque and push the root into it.

            queue = collections.deque([root])

 

Then, we will create a loop that will run while the queue still has nodes we need to process.

            while queue:

 

Before processing any nodes, we will first reset the right_most pointer to none and count the nodes that are currently in the queue so that we know how long our iteration should be for the given level.

                right_most = None
                level_width = len(queue)

 

Now we can start writing the main BFS logic.

For each node in the current level, we will pop the node off of the queue, label it as the right_most node of the current level, append its value to the output array and then push all of its children into the queue.

                for _ in range(level_width):
                    node = queue.popleft()
                    right_most = node
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)

 

If the right_most node was set in the iteration, we will append the value of the node it was last pointed at.

                if right_most:
                    output.append(right_most.val)

Now, all we need to do is make the initial function call by passing the root.

        bfs(root)

 

Once the BFS is complete, we will return the output array of all the rightmost values.

        return output

Recursive Depth-First Search

The DFS solution is a little trickier in theory but easier to implement.

The basic idea is we will only have one node per level that we would be able to see from the right-side view.  From that requirement, we can use the length of the output as an indicator for whether or not the farthest right node has been picked yet for the given level.   

We'll run the preorder DFS on the right child first of each node so that we favor the right side of the tree in our search.  If the length of the output is the same as the level, then that means we haven't chosen a node from the current level yet so we can append the first node seen in our search since the DFS path will go to the farthest path down the right side of the tree before moving toward any left paths.

First off, if there is no root that was input, we have nothing to see on the right side so we are done.

        if not root:
            return root

 

Otherwise, we will start by initializing our output array.

        output = []

Next, we will create our recursive dfs function.

The function will take a level integer so that we can keep track of the level each node is on, and it will also take the node it is being called on.

        def dfs(node: TreeNode, level: int) -> None:

 

If the current node is null, we have reached the end of a valid path so we will return.

            if not root:
                return 

 

Otherwise, we will check if the length of the output is the same as the level value.

For example, if the length of the output is zero and we are on level zero, the root level, we know that we haven't picked a node from this level yet so we will pick the first node we see in our DFS.  

Notice we put the base case before the function calls in the function.  This ensures that the DFS is picking values as it moves down the search.

            if level == len(output):
                output.append(node.val)

 

After appending a value or not, we will continue the DFS on the right node first then the left while incrementing the level value by one.

            if node.right:
                dfs(node.right, level + 1)
            if node.left:
                dfs(node.left, level + 1)

Now that we have the function built, we just need to make the initial call by passing the root and the initial level value of zero.

Once the DFS is complete, we will return all of the rightmost values.

        dfs(root, 0)
        return output