Binary Tree Views: Left and Right

1. What are Left and Right Views?

Imagine you are standing to the far left or far right of a binary tree. The "view" is the set of nodes you can see from that perspective, from top to bottom. Nodes at a lower level might be hidden behind nodes at an upper level.

Our goal is to write a function that returns a list of these nodes' values.

2. The Core Idea: First Node at Each Level

If you think about the problem, the nodes that form the left or right view share a common property:

• Left View: Consists of the first node at every level.
• Right View: Consists of the last node at every level.

This observation gives us two potential paths forward:

1. Level-Order Traversal (BFS): We can traverse the tree level by level using a queue. For each level, we can simply pick the first node for the left view or the last node for the right view. This is a perfectly valid and intuitive approach.
2. Depth-First Traversal (DFS): We can use a recursive approach. This is often more elegant and space-efficient (using the call stack, which is O(Height) vs. O(Width) for the BFS queue). But how do we know which node is "first" or "last" at a level during a recursive traversal? This requires a clever trick.

Given your goal of interview preparation, mastering the efficient recursive (DFS) solution is crucial, as it showcases a deeper understanding of traversal patterns. We will focus on this approach.

3. Finding the Right View: A "Reverse" Pre-order Traversal

To get the right view, we want to encounter the rightmost node at each level first. A standard pre-order traversal goes Root -> Left -> Right. This prioritizes the left side. What if we reverse the order of the recursive calls?

Let's use a Root -> Right -> Left traversal.

With this traversal order, the very first time we visit any level, we are guaranteed to be at its rightmost node. We just need a way to keep track of the levels we've already added to our result.

The following video from "take U forward" explains this elegant solution perfectly. It uses a simple but powerful trick to track visited levels without any extra data structures.

Dissecting the Recursive Logic

Let's break down the core components of the algorithm you just saw.

1. Helper Function: We use a recursive function, say rightViewRec(TreeNode node, int level, List<Integer> result).
2. Base Case: If node == null, we simply return.
3. The "First Visit" Trick: This is the most important part. Before making recursive calls, we check: if (result.size() == level).
   • level starts at 0 for the root.
   • result.size() tells us how many levels for which we have already stored a node.
   • If result.size() equals level, it means we are visiting this level for the very first time. Since our traversal order is Root -> Right -> Left, this first-encountered node must be the rightmost one. So, we add it to our result list.
4. Recursive Calls: We make the calls in a specific order to prioritize the right side:
   • First, rightViewRec(node.right, level + 1, result).
   • Then, rightViewRec(node.left, level + 1, result).

Java Implementation for Right View

Here is the clean Java code that implements this logic. You will find this is a very common pattern in top-tier interviews.

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

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

public class Solution {

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

    private void rightViewRec(TreeNode node, int level, List<Integer> result) {
        // Base case: we've gone past a leaf node
        if (node == null) {
            return;
        }

        // If this is the first node we've seen at this level
        if (level == result.size()) {
            result.add(node.val);
        }

        // Recurse for the right subtree first
        rightViewRec(node.right, level + 1, result);
        
        // Then recurse for the left subtree
        rightViewRec(node.left, level + 1, result);
    }
}

• Time Complexity: O(N), as we visit every node exactly once.
• Space Complexity: O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, this is O(N), but for a balanced tree, it's O(log N).

4. Finding the Left View: A Simple Adaptation

Now for the left view. Based on the logic we just established, how would you adapt the algorithm?

Exactly! We simply change the traversal order to the standard pre-order: Root -> Left -> Right.

Java Implementation for Left View

The code is nearly identical. Only the order of the two recursive calls is swapped.

public class Solution {

    public List<Integer> leftSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        leftViewRec(root, 0, result);
        return result;
    }

    private void leftViewRec(TreeNode node, int level, List<Integer> result) {
        if (node == null) {
            return;
        }

        if (level == result.size()) {
            result.add(node.val);
        }

        // Recurse for the left subtree first
        leftViewRec(node.left, level + 1, result);
        
        // Then recurse for the right subtree
        leftViewRec(node.right, level + 1, result);
    }
}

This elegant symmetry between the left and right view solutions is what makes the recursive approach so powerful.

5. Alternative: The Iterative Level-Order Approach

While the recursive DFS is often preferred for its conciseness, it's essential to also know the iterative BFS approach, as interviewers might specifically ask for it or for non-recursive solutions.

The idea is to perform a standard level-order traversal. In each level, we identify and add only the first node to our list for the left view.

To adapt the iterative approach for the right view, you would simply add the node to the result when i == currLevelNodeCount (i.e., the last node in the level's for-loop).

      1
     / \
    2   3
     \   \
      5   4

Conclusion

In this lesson, we tackled the left and right view problems, adding two important patterns to your tree algorithm toolkit.

Key Takeaways:

• The left/right view of a binary tree consists of the first/last node at each level.
• The most elegant solution is a recursive DFS that combines a specific traversal order with level tracking.
  • Right View: Use a Root -> Right -> Left traversal.
  • Left View: Use a Root -> Left -> Right (standard pre-order) traversal.
• The condition if (result.size() == level) is a space-efficient trick to identify the first time you visit a new level during the traversal.
• An iterative level-order (BFS) approach is a valid and important alternative to know.

Preview of the Next Lesson:
We will continue with "view" problems and move on to the top and bottom views of a binary tree. These problems introduce a new dimension: horizontal distance from the root. You'll see how we can augment our traversal state to track both vertical level and horizontal distance to solve these more complex challenges.