LeetCode 199 | Binary Tree Right Side View | Python | Solution

If you know about the level order traversal algorithm, finding the right-side view of a binary tree becomes easy for you. This problem is nothing but a simple extended version of that. If you want to know about Level Order Traversal, I will encourage you to read this blog.

LeetCode 199

The problem description is pretty straightforward. In the level order traversal algorithm, we traverse nodes of a binary tree level by level. So, the first level is the root of a tree. And the second level is the two children of that root, and the third is the children of those two. For example:

                                  1
                                /   \
                              2       3
                            /  \     /  \
                           4    5   6    7

So the levels of the above binary tree will be:

1
2, 3
4, 5, 6, 7

From these levels, we can get the right node of each. That is the right-side view.

I also encourage you to see this LeetCode solution. This one is also an implementation of level order traversal. Here you will find how we can get each level standalone way. As we get each level in the queue as standalone data, we can get the right-most node without difficulty.

You can get the right-most node in many ways. I will show two of them. So let’s see the solution in code to get a better understanding.

# 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: Optional[TreeNode]) -> List[int]:
        
        if not root:
            return []

        result = []
        queue = deque()
        queue.append(root)

        while queue:

            level_length = len(queue)

            # Option 1
            # result.append(queue[-1].val)

            for i in range(level_length):

                node = queue.popleft()

                # Option 2
                if i == level_length - 1:
                    result.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
        return result

The time complexity of this solution is O(n), where n is the number of nodes.

Tags: Binary TreeLeetCodeProblem SolvingPythonSolutionTree