199. Binary Tree Right Side View#

Difficulty: Medium

Link to Problem: To see the Binary Tree Right Side View problem on LeetCode, click here!

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.

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].

  • -100 <= Node.val <= 100

Solution:#

Here’s a Python function to solve this problem:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root):
    if not root:
        return []  # If the tree is empty, return an empty list.

    result = []  # Initialize a list to store the right side view values.
    queue = [root]  # Initialize a queue for level-order traversal with the root node.

    while queue:
        # Get the number of nodes at the current level.
        level_size = len(queue)

        # Traverse all nodes at the current level and add the rightmost node to the result.
        for i in range(level_size):
            node = queue.pop(0)  # Dequeue the first node from the queue.

            # If it's the rightmost node at this level, add its value to the result.
            if i == level_size - 1:
                result.append(node.val)

            # Add the children of the current node to the queue.
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result  # Return the list of right side view values.

Explanation:#

  1. We start with a binary tree represented using a TreeNode class. Each node has a value (val) and can have a left child (left) and a right child (right).

  2. The rightSideView function takes the root node of the binary tree as input and returns a list of values representing the nodes you can see when standing on the right side of the tree.

  3. We check if the root is None, which means the tree is empty. If it’s empty, we return an empty list because there are no nodes to see.

  4. We initialize an empty list called result to store the right side view values.

  5. We initialize a queue called queue with the root node. This queue is used for a level-order traversal of the tree.

  6. We enter a while loop that continues until the queue is empty. Inside this loop, we perform the following steps for each level of the tree:

    a. We determine the number of nodes at the current level by getting the length of the queue. This is important for processing nodes at the same level together.

    b. We then iterate through the nodes at the current level using a for loop. For each node in the level, we dequeue it from the queue using queue.pop(0).

    c. If the node we dequeue is the rightmost node at the current level (determined by i == level_size - 1), we add its val to the result list. This is because, when standing on the right side of the tree, you can see the rightmost node at each level.

    d. We enqueue the left and right children of the current node (if they exist) to the queue. This ensures that we process the next level in the subsequent iterations of the while loop.

  7. After processing all levels of the tree, the result list contains the values of the rightmost nodes in each level, ordered from top to bottom.

  8. Finally, we return the result list as the output of the function, which represents the right side view of the binary tree.

The code effectively performs a level-order traversal of the binary tree while keeping track of the rightmost nodes at each level and adding them to the result list. This ensures that we obtain the correct order of nodes visible from the right side of the tree.

Test cases#

# Example 1: 

# Construct the tree
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.right = TreeNode(5)
root1.right.right = TreeNode(4)
print(rightSideView(root1))

[1, 3, 4]

# Example 2:

root2 = TreeNode(1)
root2.right = TreeNode(3)
print(rightSideView(root2))

[1, 3]

# Example 3:
# Creating a new tree for this example
root = None
result = rightSideView(root)
print(result)

[]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the given code:

Time Complexity:

The time complexity of the code is O(N), where N is the number of nodes in the binary tree. Here’s why:

  1. We perform a level-order traversal of the tree using a queue. In the worst case, we visit all nodes once, which takes O(N) time since we visit each node exactly once.

  2. For each node, we perform constant-time operations like dequeuing it from the queue, checking if it’s the rightmost node at the current level, and enqueuing its children (if they exist). These operations do not depend on the size of the tree, so they do not contribute to the overall time complexity.

Therefore, the dominant factor in the time complexity is the level-order traversal, making it O(N).

Space Complexity:

The space complexity of the code is also O(N). Here’s why:

  1. We use a queue to perform level-order traversal. In the worst case, the queue can contain all nodes at the maximum width of the tree, which can be up to N/2 nodes for a completely unbalanced tree. Therefore, the space required for the queue is O(N).

  2. The result list stores the values of the rightmost nodes. In the worst case, when the binary tree is a complete binary tree, it can have roughly N/2 rightmost nodes. Therefore, the space required for the result list is also O(N).

  3. Other auxiliary variables like level_size, i, and node require only constant space and do not depend on the size of the tree.

Combining the space used by the queue and the result list, we get a space complexity of O(N).

In summary, the code has a time complexity of O(N) and a space complexity of O(N), where N is the number of nodes in the binary tree. These complexities are efficient and scale linearly with the size of the input tree.

Challenging Exercises:#

  1. Variant with Left Side View: Modify the code to find and return the values of nodes visible from the left side of the binary tree instead of the right side.

  2. Zigzag Right Side View: Extend the code to return the right side view values in a zigzag order. In a zigzag order, you alternate between starting from the rightmost node at level 0, then the leftmost at level 1, rightmost at level 2, and so on.