Obsidian Notes

9. Binary Tree Right Side View

3 min read

Description

Binary Tree Right Side View

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 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:

Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:

Example 3:
Input: root = [1,null,3]
Output: [1,3]

Example 4:
Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Approach

  • Do the simple BFS level order traversal and usually you end up at the right most side by the time you reach the end of traversing the level
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
 
        while(!q.isEmpty()) {
            TreeNode right = null;
            for(int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                if(n != null) {
                    right = n;
                    q.add(n.left);
                    q.add(n.right);
                } 
            }
            if (right != null)
                view.add(right.val);
        }
        return view;    
    }
}

Approach 1: BFS Level-Order Traversal ( Time, Space)

Intuition

Traverse the binary tree level-by-level using a queue (ArrayDeque). For each level, iterate through all of its nodes and pick the last node in that level, as it is the rightmost node visible from the right side.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
 
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
 
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
 
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
 
            for (int i = 0; i < levelSize; i++) {
                TreeNode curr = queue.poll();
 
                // If it's the last node of the current level, add it to the result
                if (i == levelSize - 1) {
                    result.add(curr.val);
                }
 
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
        }
 
        return result;
    }
}

Complexity

  • Time Complexity: — Every node in the binary tree is processed exactly once.
  • Space Complexity: — Max queue size is bounded by the maximum number of nodes at any level (up to for a complete binary tree).

Approach 2: DFS Modified Preorder Traversal ( Time, Space)

Intuition

Traverse the tree using Depth-First Search prioritizing Right child before Left child (). Track the current depth level: whenever depth == result.size(), it means this is the first time reaching this level, which is guaranteed to be the rightmost node.

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }
 
    private void dfs(TreeNode node, int depth, List<Integer> result) {
        if (node == null) return;
 
        // First time visiting this depth level -> must be the rightmost node
        if (depth == result.size()) {
            result.add(node.val);
        }
 
        dfs(node.right, depth + 1, result); // Visit Right child first
        dfs(node.left, depth + 1, result);  // Visit Left child second
    }
}

Complexity

  • Time Complexity: — Every node is visited once during traversal.
  • Space Complexity: worst-case call stack depth for a skewed tree ( for a balanced tree).

Easy Memory Rule

“BFS: Pick the last element of every level queue, OR DFS: Go Right before Left and add when depth == result.size()!”

Backlinks