Binary Tree Right Side View

Medium

Binary Tree Right Side View

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, and if so, what should I return?
What is the range of values for the node values in the tree?
Is the tree guaranteed to be a binary tree, or could it be a more general tree structure?
By 'right side', do you mean the rightmost node as we traverse level-by-level using a standard level-order traversal (BFS)?
If the tree is skewed to the left such that some levels have no right node, should I include the last (leftmost) node encountered on that level in the result?

Brute Force Solution

Approach

Imagine shining a light from the right side of the tree. The brute force method involves checking every node at each level to see if it's the first one you'd see from the right. We accomplish this by systematically exploring all possible paths in the tree level by level.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root node).
Explore all nodes at each level of the tree, going from top to bottom.
For each level, look at the nodes from right to left. The very first node you encounter at each level is the one you can see from the right side.
Save the value of that right-most visible node.
Continue this process for every level of the tree.
Once you have inspected every level, you'll have a list of the right-most visible nodes at each level. This list is the right side view of the tree.

Code Implementation

def right_side_view_brute_force(root):
    if not root:
        return []

    right_view = []
    nodes_at_level = [root]

    while nodes_at_level:
        level_size = len(nodes_at_level)
        rightmost_node_found = False

        # Iterate through the current level in reverse order
        for index in range(level_size - 1, -1, -1):
            current_node = nodes_at_level[index]

            # Check if we have already found the rightmost node
            if not rightmost_node_found:
                right_view.append(current_node.val)

                # Mark that we have found the rightmost node
                rightmost_node_found = True

        next_level_nodes = []

        # Add children for the next level's processing
        for node in nodes_at_level:

            if node.left:

                # Add left node
                next_level_nodes.append(node.left)

            if node.right:

                # Add right node
                next_level_nodes.append(node.right)

        nodes_at_level = next_level_nodes

    return right_view

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the binary tree level by level using a breadth-first search (BFS) approach. In the worst-case scenario, it visits each of the n nodes in the tree. For each level, it iterates through the nodes present at that level, but each node is enqueued and dequeued only once. Therefore, the time complexity is proportional to the number of nodes in the tree, which is O(n).

Space Complexity

O(W) – The described brute force approach iterates level by level, implying a breadth-first traversal. This suggests a queue data structure to manage the nodes to be visited at each level. In the worst case, the queue might hold all nodes at the widest level of the tree. Therefore, the auxiliary space is proportional to the maximum width (W) of the binary tree. Thus, the space complexity is O(W), where W is the maximum width of the tree, and in a complete binary tree W would be N/2, giving O(N).

Optimal Solution

Approach

To find the rightmost node at each level of a binary tree, we'll use a level-by-level exploration strategy. This approach ensures we always discover the rightmost node before any other node on the same level, giving us the 'right side view'.

Here's how the algorithm would work step-by-step:

Start at the very top (root) of the tree.
Imagine processing the tree one layer at a time, like peeling an onion.
For each layer, grab the rightmost node before moving to the next layer down.
Move to the next layer of nodes using a systematic way of checking all nodes in that layer.
Repeat the process of grabbing the rightmost node for each layer, working your way down the tree.
Keep doing this until you reach the bottom of the tree (no more layers).
The list of rightmost nodes you've collected represents the 'right side view' of the tree.

Code Implementation

from collections import deque

def binary_tree_right_side_view(root_node):
    right_side_view = []

    if not root_node:
        return right_side_view

    node_queue = deque([root_node])

    while node_queue:
        level_length = len(node_queue)

        # Iterate through all nodes at current level.
        for index in range(level_length):
            current_node = node_queue.popleft()

            # The last node processed is rightmost.
            if index == level_length - 1:
                right_side_view.append(current_node.val)

            # Add left child to queue for next level.
            if current_node.left:
                node_queue.append(current_node.left)

            # Add right child to queue for next level.
            if current_node.right:
                node_queue.append(current_node.right)

    return right_side_view

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once to determine the right side view. We are using a level-order traversal (breadth-first search) to explore the tree level by level. Each node is enqueued and dequeued a constant number of times. Therefore, the time complexity is directly proportional to the number of nodes n in the tree, resulting in O(n) time complexity.

Space Complexity

O(W) – The provided solution uses a level-order traversal, which employs a queue (implicitly described as a systematic way of checking all nodes in that layer) to process nodes level by level. In the worst-case scenario, the queue might hold all nodes at the widest level of the tree. Therefore, the auxiliary space is proportional to the maximum width (W) of the binary tree. Thus, the space complexity is O(W).

Edge Cases

Case	How to Handle
Null or empty tree	Return an empty list immediately because there are no nodes to view from the right side.
Tree with only a root node	Return a list containing only the root node's value because it is the only visible node.
Completely skewed tree (left or right)	The algorithm should correctly identify the rightmost node at each level even in skewed trees; breadth-first search will handle it.
Perfectly balanced tree	The algorithm will efficiently process a balanced tree, correctly identifying the rightmost node at each level.
Tree with duplicate values	Duplicate values do not affect the algorithm's logic as it focuses on the rightmost node at each level, regardless of its value.
Tree with negative values	The algorithm should work correctly with negative node values, as value comparisons aren't the primary logic.
Large tree (scalability)	Using a level-order traversal (BFS) provides a scalable solution with O(N) time complexity where N is the number of nodes.
Tree with a wide variance in level depths	Breadth-first search efficiently handles varied level depths ensuring each rightmost node is correctly captured.