L24. Right/Left View of Binary Tree | C++ | Java

This chapter covers the algorithmic approach to finding the Right View and Left View of a binary tree. We explore both the conceptual mechanics and optimal recursive implementations in C++ and Java, balancing code brevity with optimal time and space complexities.

1. Why Do We Need Tree Views? (Problem Statement & Status Quo)

When visualizing a binary tree from a specific 2D perspective (such as standing directly in front and looking from the right or left flank), certain nodes obstruct others behind them.

• The Right Side View: The set of nodes visible when looking at the binary tree strictly from the right side.
• The Left Side View: The set of nodes visible when looking at the binary tree strictly from the left side.

Example Tree Layout

Consider the following binary tree configuration:

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

• Right-side observation perspective:
  • Level 0: Node 1 is visible.
  • Level 1: Node 3 is visible (node 2 is hidden directly behind 3 from this angle).
  • Level 2: Node 7 is visible (nodes 4 and 5 are hidden behind 7).
  • Level 3: Node 6 is visible.
• Resulting Right View Sequence: [1, 3, 7, 6]

2. Core Mental Model: Level-Wise Traversal & Visibility

To solve the right side view, let's analyze what properties define the visible nodes:

1. Level-by-Level Last Node: The right view consists precisely of the last node of every level when traversing left-to-right.
2. First Node via Reverse Pre-Order: If we reverse our traversal direction and move right-to-left (visiting the right subtree before the left subtree), the first node we encounter at every level is guaranteed to be our Right View node.

3. Naive vs. Optimal Approach: Level Order vs. Recursive Pre-Order

When deciding how to implement the traversal, we evaluate two standard paradigms:

Note: While an iterative Level Order traversal works, interviews favor the recursive reverse pre-order traversal because it achieves the exact same time complexity ($O(N)$) while maintaining a significantly cleaner, shorter, and more interview-friendly codebase.

4. Step-by-Step Recursive Algorithm & The Data Structure Trick

To capture only the first node encountered at each level without duplicate entries, we employ a clever state-tracking check using our answer list/vector (ds):

• The Core Condition:

• Why it works: Since we traverse right-first, the very first time our recursive function dives into a brand-new depth level, the current depth (level) will exactly equal the current number of elements already stored in our data structure (ds.size()).
• Therefore, we instantly push that node into our data structure. Subsequent nodes visited at that same level will find that ds.size() is already greater than level, and they will be safely ignored.

5. Complete Dry Run Walkthrough

Let's trace the recursive Root -> Right -> Left execution on our sample tree:

        1
       / \
      2   3
         / \
        5   7
       /
      6

1. Initial Call: rightView(root = 1, level = 0)
   • level (0) == ds.size() (0) -> True.
   • Add 1 to ds. (ds = [1])
2. Explore Right Subtree: rightView(node = 3, level = 1)
   • level (1) == ds.size() (1) -> True.
   • Add 3 to ds. (ds = [1, 3])
3. Explore Right Subtree of 3: rightView(node = 7, level = 2)
   • level (2) == ds.size() (2) -> True.
   • Add 7 to ds. (ds = [1, 3, 7])
4. Explore Right of 7: Encounters null, returns.
5. Explore Left of 7: Encounters null, returns. Backtrack to 3.
6. Explore Left of 3: rightView(node = 5, level = 2)
   • level (2) == ds.size() (3) -> False (Level 2 already populated by node 7). Skip adding.
7. Explore Right of 5: Encounters null, returns.
8. Explore Left of 5: rightView(node = 6, level = 3)
   • level (3) == ds.size() (3) -> True.
   • Add 6 to ds. (ds = [1, 3, 7, 6])
9. Backtrack all the way up to root 1, then invoke Left Subtree: rightView(node = 2, level = 1)
   • level (1) == ds.size() (4) -> False (Level 1 already populated by node 3). Skip adding.

Final Right View output: [1, 3, 7, 6]

6. Production-Ready Code Implementation

C++ Implementation

#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    void recursion(TreeNode* node, int level, std::vector<int>& res) {
        // Base Case: If node is null, terminate recursion branch
        if (node == nullptr) {
            return;
        }
        
        // If this is the first time we reach this level, record the node value
        if (res.size() == level) {
            res.push_back(node->val);
        }
        
        // Reverse Pre-Order Traversal: Root -> Right -> Left
        recursion(node->right, level + 1, res);
        recursion(node->left, level + 1, res);
    }

public:
    std::vector<int> rightSideView(TreeNode* root) {
        std::vector<int> res;
        recursion(root, 0, res);
        return res;
    }
};

Java Implementation

import java.util.List;
import java.util.ArrayList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private void recursion(TreeNode node, int level, List<Integer> res) {
        // Base Case: If node is null, return
        if (node == null) {
            return;
        }
        
        // Check if we are visiting this level for the first time
        if (res.size() == level) {
            res.add(node.val);
        }
        
        // Reverse Pre-Order Traversal: Root -> Right -> Left
        recursion(node.right, level + 1, res);
        recursion(node.left, level + 1, res);
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        recursion(root, 0, res);
        return res;
    }
}

Design Note for Left View: To transform the Right View implementation into a Left View algorithm, simply invert the recursive exploration order from Root -> Right -> Left to Root -> Left -> Right.

7. Summary and Key Takeaways

• Problem Definition: The Right View (or Left View) represents the sequence of nodes visible when looking at a binary tree from the respective outer edge.
• Key Insight: The right view corresponds precisely to the last node of every level, which can be efficiently captured by visiting nodes from right-to-left.
• Traversal Strategy: Use a Reverse Pre-Order traversal (Root -> Right -> Left) for the Right View, and standard Pre-Order (Root -> Left -> Right) for the Left View.
• Level Tracking Trick: Compare the current recursive depth (level) against the data structure size (ds.size()). A match indicates the first encounter of a node at that level.
• Time Complexity: $O(N)$, where $N$ is the total number of nodes in the binary tree, as every node is visited exactly once.
• Space Complexity: $O(H)$ auxiliary stack space, where $H$ is the height of the tree (becoming $O(N)$ in the worst-case scenario of a completely skewed tree).