Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

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

Given a binary search tree, return the left side view from bottom to top, and the right side view from top to bottom. Ensure there are no duplicates.

Asked at:

Meta

DESCRIPTION

Given a binary search tree, return the left side view from bottom to top, and the right side view from top to bottom. Ensure there are no duplicates.

Input:

root = [4,2,6,1,3,5,7]

Output:

[1,2,4,6,7]

Explanation: Left view from bottom to top: [1,2,4]. Right view from top to bottom: [4,6,7]. Combined with duplicates removed: [1,2,4,6,7]

Constraints:

The number of nodes in the tree is in the range [0, 100]
-100 <= Node.val <= 100
The tree is a valid binary search tree
Node values may not be unique in the final result, but duplicates should be removed

Understanding the Problem

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

Left side view from bottom to top: Looking from the left, what nodes do we see at each level, starting from the bottom?
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:

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)?

Brute Force Approach

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.

Visualization

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

Start finding left and right side views of BST

0 / 72

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We visit each node once during DFS traversal, then iterate through the depth levels to construct the views

Space Complexity: O(n) We store all nodes in hash maps organized by depth, plus the recursion stack for DFS which can be O(h) where h is the height

Building Intuition

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.

Common Mistakes

Forgetting to handle the empty tree case, which should return an empty result

Not properly reversing the left view (it should be bottom-to-top, not top-to-bottom)

Failing to remove duplicates when the same node appears in both views (e.g., when the tree has only one node)

Using DFS without properly tracking levels, which makes it harder to identify the leftmost and rightmost nodes at each level

Not considering that the root node appears in both views and must be deduplicated in the final result

Optimal Solution

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.

Visualization

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)

Start tree side views algorithm

0 / 64

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We visit each node exactly once during the BFS traversal, processing all n nodes in the tree

Space Complexity: O(w) The queue stores at most w nodes where w is the maximum width of the tree (number of nodes at the widest level), plus O(h) for storing the result where h is the height

What We've Learned

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.

Test Your Understanding

Why is tree the right data structure for this problem?

tree provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Meta

Manager

Late October, 2025

Meta

Senior

Phonescreen

Mid October, 2025

Meta

Staff

Get Premium to View All 10+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

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

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact