☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Right/Left View of Binary Tree

Medium TUF ID 2782 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree. Stand to the right of the tree and list the nodes you can see from top to bottom: that is the right view. On every level you see exactly one node, the rightmost node of that level. The left view is the same idea from the other side: the leftmost node of every level.

Return each view as a list of values, one per level, starting from the root. An empty tree has an empty view. LeetCode asks only for the right view; the left view (a GeeksforGeeks classic) uses the same technique with one change, so both are covered here.

Constraints: up to 10^5 nodes (LeetCode allows up to 100); values are arbitrary integers.

Example 1

      1
    /   \
   2     3
    \     \
     5     4

right view = [1, 3, 4]
left view  = [1, 2, 5]

On level 2 the nodes are 5 and 4. From the right you see 4; from the left you see 5.

Example 2

      1
    /   \
   2     3
  /
 4

right view = [1, 3, 4]
left view  = [1, 2, 4]

4 is a left child, yet it appears in the right view. Nothing on its level is to its right, so nothing blocks it. “Right view” is about the rightmost node of a level, not about right children.

Approach 1: Level-order traversal (BFS)

Intuition. The definition is level by level, so a level-order traversal fits naturally. If we process the queue one level at a time (record size = q.size() before the inner loop), the nodes of each level come out from left to right. The last node of the batch is the rightmost node of that level, which is the right view entry. The first node of the batch is the left view entry.

Algorithm (right view).

  1. If the tree is empty, return an empty list.
  2. Push the root.
  3. While the queue is not empty: let size be the queue size. Pop size nodes; when i == size - 1, record the node’s value. Push each node’s children, left then right.
  4. Return the recorded values.
static List<Integer> rightViewBfs(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int size = q.size();                                  // number of nodes on the current level
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (i == size - 1) ans.add(node.val);             // last node of this level
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
    }
    return ans;
}

For the left view, record the node when i == 0 instead.

static List<Integer> leftViewBfs(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (i == 0) ans.add(node.val);                    // first node of this level
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
    }
    return ans;
}

Complexity. Time O(n): every node is enqueued and dequeued once. Space O(w), where w is the maximum number of nodes on one level. For a complete tree that is about n / 2.

Approach 2: Recursive DFS with a depth counter

Intuition. We can avoid the queue. Do a preorder walk that visits the right child before the left one. Then, for every depth, the first node the walk reaches at that depth is the rightmost node of that level. Why? For any two nodes on the same level, their lowest common ancestor has one in its right subtree and one in its left subtree, and our walk finishes the right subtree first.

How do we know a depth is reached “for the first time”? Keep the answer list itself as the record. When the walk is at depth d, the list already holds one value for each depth 0 .. size - 1 that has been seen. A walk can only reach depth d after visiting depth d - 1 (the parent), so depths are discovered in order, and depth == ans.size() is true exactly on the first visit to a new depth.

For the left view, visit the left child first; everything else is identical.

Algorithm (right view).

  1. Call rightDfs(root, 0, ans) with an empty list.
  2. In rightDfs: if the node is null, return. If depth == ans.size(), append the value.
  3. Recurse into node.right, then node.left, both with depth + 1.
static List<Integer> rightViewDfs(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    rightDfs(root, 0, ans);
    return ans;
}

static void rightDfs(TreeNode node, int depth, List<Integer> ans) {
    if (node == null) return;
    if (depth == ans.size()) ans.add(node.val);               // first time we reach this depth
    rightDfs(node.right, depth + 1, ans);
    rightDfs(node.left, depth + 1, ans);
}

static List<Integer> leftViewDfs(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    leftDfs(root, 0, ans);
    return ans;
}

static void leftDfs(TreeNode node, int depth, List<Integer> ans) {
    if (node == null) return;
    if (depth == ans.size()) ans.add(node.val);
    leftDfs(node.left, depth + 1, ans);
    leftDfs(node.right, depth + 1, ans);
}

Dry run of the right view on Example 1:

call depth ans.size() before action ans after
1 0 0 first at depth 0, add [1]
3 1 1 first at depth 1, add [1, 3]
4 2 2 first at depth 2, add [1, 3, 4]
2 1 3 depth 1 already seen [1, 3, 4]
5 2 3 depth 2 already seen [1, 3, 4]

Complexity. Time O(n): each node is visited once. Space O(h) for the recursion stack, where h is the height of the tree (besides the output list).

Which one to choose. Both are linear. The DFS uses O(h) memory and the BFS uses O(w). A balanced tree has small height (log n) but a wide bottom level (n / 2), so the DFS is lighter there. A long chain is the reverse: height n but width 1. In Java, the DFS on a chain of 10^5 nodes can overflow the call stack, so the BFS is the safer default when the tree may be very deep.

Edge cases and pitfalls