Binary Tree Right Side View

199.Binary Tree Right Side View

Tree

Binary Tree

Breadth-First Search

Depth-First Search

Problem Statement:

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.

Example:

Input:

root = [1,2,3,null,5,null,4]

→

Output:

[1,3,4]

Visible nodes from right side are 1, 3, and 4

Algorithm:

1. BFS: Process level by level, add rightmost node
2. DFS: Process right first, add first node at each depth
3. Both maintain order from top to bottom
4. Handle null case separately

Complexity:

Time: O(n) | Space: O(w) where w is max width of tree

Java Solution:

// BFS Solution
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    
    // Process level by level
    while (!q.isEmpty()) {
        int n = q.size();
        
        // Process each level and add rightmost node
        for (int i = 0; i < n; i++) {
            TreeNode curr = q.poll();
            if (i == n - 1) result.add(curr.val);
            
            if (curr.left != null) q.add(curr.left);
            if (curr.right != null) q.add(curr.right);
        }
    }
    return result;
}

// DFS Solution
public List<Integer> rightSideViewDFS(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    rightView(root, result, 0);
    return result;
}

private void rightView(TreeNode curr, List<Integer> result, int currDepth) {
    // Base case: null node
    if (curr == null) return;
    
    // First node at this depth (from right)
    if (currDepth == result.size())
        result.add(curr.val);
    
    // Process right subtree first
    rightView(curr.right, result, currDepth + 1);
    rightView(curr.left, result, currDepth + 1);
}

Python Solution:

# BFS Solution
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
        
    result = []
    q = deque([root])
    
    # Process level by level
    while q:
        size = len(q)
        
        # Process each level and add rightmost node
        for i in range(size):
            curr = q.popleft()
            if i == size - 1:
                result.append(curr.val)
                
            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)
                
    return result

# DFS Solution
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    result = []
    
    def rightView(node: TreeNode, depth: int) -> None:
        # Base case: null node
        if not node:
            return
            
        # First node at this depth (from right)
        if depth == len(result):
            result.append(node.val)
            
        # Process right subtree first
        rightView(node.right, depth + 1)
        rightView(node.left, depth + 1)
    
    rightView(root, 0)
    return result

C++ Solution:

class Solution {
public:
    // BFS Solution
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        
        // Process level by level
        while (!q.empty()) {
            int size = q.size();
            
            // Process each level and add rightmost node
            for (int i = 0; i < size; i++) {
                TreeNode* curr = q.front();
                q.pop();
                
                if (i == size - 1) result.push_back(curr->val);
                
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
        return result;
    }
    
    // DFS Solution
    vector<int> rightSideViewDFS(TreeNode* root) {
        vector<int> result;
        rightView(root, result, 0);
        return result;
    }
    
private:
    void rightView(TreeNode* curr, vector<int>& result, int currDepth) {
        // Base case: null node
        if (!curr) return;
        
        // First node at this depth (from right)
        if (currDepth == result.size())
            result.push_back(curr->val);
            
        // Process right subtree first
        rightView(curr->right, result, currDepth + 1);
        rightView(curr->left, result, currDepth + 1);
    }
};