Find the Left and Right Side View of a Binary Search Tree

Let's understand what we're being asked to do. We have a binary search tree (BST) and need to return two views:

1. Left side view from bottom to top: Looking from the left, what nodes do we see at each level, starting from the bottom?
2. Right side view from top to bottom: Looking from the right, what nodes do we see at each level, starting from the top?

For example, given a BST like:

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

Left side view (bottom to top): [1, 2, 4] - we see node 1 at the bottom level, node 2 at the next level up, and node 4 at the root.

Right side view (top to bottom): [4, 6, 7] - we see node 4 at the root, node 6 at the next level down, and node 7 at the bottom level.

Important constraint: Ensure there are no duplicates in the final result. If a node appears in both views, include it only once.

Edge cases to consider: What if the tree is empty? What if the tree has only one node? What if the tree is skewed (all nodes on one side)?

Use depth-first search to traverse the tree and track the depth of each node. Maintain two hash maps: one for the leftmost node at each depth, and one for the rightmost node at each depth. After traversal, extract the left view by iterating depths from bottom to top, and the right view by iterating depths from top to bottom. Finally, combine both views and remove duplicates using a set. This approach works but requires multiple passes through the data structures.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def tree_side_views(root):
    """
    Returns left side view (bottom to top) and right side view (top to bottom)
    with no duplicates using brute force approach with multiple passes.
    """
    if not root:
        return []
    
    # Hash maps to store leftmost and rightmost nodes at each depth
    left_view_map = {}
    right_view_map = {}
    
    # DFS to traverse tree and populate hash maps
    def dfs(node, depth):
        if not node:
            return
        
        # Store leftmost node at this depth (first visit)
        if depth not in left_view_map:
            left_view_map[depth] = node.val
        
        # Always update rightmost node at this depth (last visit)
        right_view_map[depth] = node.val
        
        # Traverse left subtree first, then right
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    
    # Start DFS from root at depth 0
    dfs(root, 0)
    
    # Extract left view from bottom to top (inefficient: iterate all depths)
    max_depth = max(left_view_map.keys())
    left_view = []
    for depth in range(max_depth, -1, -1):
        left_view.append(left_view_map[depth])
    
    # Extract right view from top to bottom (inefficient: iterate all depths)
    right_view = []
    for depth in range(max_depth + 1):
        if depth in right_view_map:
            right_view.append(right_view_map[depth])
    
    # Combine both views (inefficient: use list concatenation)
    combined = left_view + right_view
    
    # Remove duplicates using set (inefficient: convert to set then back to list)
    seen = set()
    result = []
    for val in combined:
        if val not in seen:
            seen.add(val)
            result.append(val)
    
    return result

To get the left and right side views, we need to visit the tree level by level. At each level, the leftmost node contributes to the left view, and the rightmost node contributes to the right view.

The key insight is that we need to know which level each node belongs to, and we need to process levels in a specific order (bottom-to-top for left view, top-to-bottom for right view).

By processing the tree level by level, we can easily identify the first node (leftmost) and last node (rightmost) at each level. This is much more efficient than trying to determine visibility through recursive depth-first traversal.

The level-order traversal naturally gives us the structure we need to extract both views in a single pass through the tree.

Imagine standing at different positions around the tree:

• Standing on the left side: You can only see the leftmost node at each level. Starting from the bottom and looking up, you record what you see.
• Standing on the right side: You can only see the rightmost node at each level. Starting from the top and looking down, you record what you see.

The challenge is to traverse the tree in a way that lets you identify these boundary nodes efficiently. Think about how you might organize nodes by their depth or level to make this easy.

Use breadth-first search (level-order traversal) with a queue to process the tree level by level. For each level, track the first node (leftmost) and last node (rightmost). Store all levels in a list, then extract the left view by taking the first node of each level from bottom to top, and the right view by taking the last node of each level from top to bottom. Use a set to combine both views and automatically handle duplicates. This approach is more intuitive and processes the tree in a single pass.

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def tree_side_views(root):
    """
    Returns combined left view (bottom-to-top) and right view (top-to-bottom)
    with no duplicates using BFS level-order traversal.
    """
    if not root:
        return []
    
    # Store all levels with their nodes
    levels = []
    queue = deque([root])
    
    # BFS to collect all levels
    while queue:
        level_size = len(queue)
        current_level = []
        
        # Process all nodes at current level
        for i in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            # Add children to queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        levels.append(current_level)
    
    # Use set to avoid duplicates
    result_set = set()
    
    # Left view: first node of each level, bottom to top
    for level in reversed(levels):
        result_set.add(level[0])
    
    # Right view: last node of each level, top to bottom
    for level in levels:
        result_set.add(level[-1])
    
    return list(result_set)

• Level-order traversal for side views: Use BFS with level tracking to capture side views of a tree - the first node at each level gives the left view, and the last node gives the right view. This is more reliable than recursive DFS because it guarantees proper level-by-level processing.
• Queue-based level separation: Track level boundaries by processing nodes in batches using `queue.size()` at the start of each level iteration - this eliminates the need for sentinel values or nested data structures to distinguish between levels.
• Directional view construction: For left view bottom-to-top, collect nodes during traversal then reverse the list; for right view top-to-bottom, append directly. This approach separates traversal logic from output formatting, making the code cleaner and less error-prone.
• Duplicate prevention through level tracking: Since each level contributes exactly one node to each side view, duplicates are impossible when using proper level-order traversal - the root appears in both views only once because it's the sole node at level 0.
• O(n) time with O(w) space trade-off: BFS requires O(w) space where w is maximum tree width (can be O(n) for degenerate trees), but guarantees O(n) time with single-pass traversal. This is optimal because you must visit every node at least once to determine visibility.
• Side view pattern extends to visibility problems: This technique applies to any problem requiring level-wise boundary detection - building floor plans, rendering 3D projections, finding visible nodes from any angle, or identifying perimeter elements in grid-based structures.