☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Right/Left View of BT

Medium TUF ID 123 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Imagine standing to the right of a binary tree and looking at it. On every level you see exactly one node, the rightmost one; everything else on that level is hidden behind it. The right view is the list of those visible nodes from the top level to the bottom. The left view is the same idea seen from the left: the leftmost node of every level. Return both (as two separate methods). An empty tree has empty views.

Constraints (LeetCode 199, right view): up to 100 nodes, values in [-100, 100]. The Java file also runs a 100000-node complete tree.

Example 1

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

Level by level the nodes are [1], [2, 3], [5, 4]. The right view takes the last of each level, the left view the first.

Example 2

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

The common mistake is to think the right view means “keep following right children”. Here 3 has no children, yet 4 is still visible from the right, because nothing else on its level stands in front of it. The view is about levels, not about pointers.

Approach 1: Level order traversal (BFS)

Intuition. Since the answer is “one node per level”, traverse the tree level by level. A queue processes nodes in breadth-first order, and if we read the queue’s size at the start of each round, that size is exactly the number of nodes on the current level. While draining those nodes, the first one dequeued is the leftmost node of the level and the last one is the rightmost. Children are enqueued left before right, so the order inside each level is left to right.

Algorithm.

  1. If the root is null, return an empty list. Otherwise enqueue the root.
  2. While the queue is not empty:
    • Let size be the queue’s current size.
    • Dequeue size nodes. Record the node at position size - 1 for the right view, or position 0 for the left view.
    • Enqueue each dequeued node’s left child, then its right child, if present.
  3. Return the recorded values.
static List<Integer> rightViewBfs(TreeNode root) {
    return viewBfs(root, true);
}

static List<Integer> leftViewBfs(TreeNode root) {
    return viewBfs(root, false);
}

static List<Integer> viewBfs(TreeNode root, boolean rightSide) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();                         // exactly the nodes of the current level
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (rightSide ? i == size - 1 : i == 0) out.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    return out;
}

Complexity. Time O(n): each node is enqueued and dequeued once. Space O(w), where w is the maximum number of nodes on one level. For a complete tree the last level holds about n / 2 nodes, so this is O(n) in the worst case.

Approach 2: Depth-first search with a depth counter

Intuition. We do not actually need whole levels; we only need the first node we meet at each depth, provided the traversal meets the visible node first. For the right view, use a depth-first order that goes to the right child before the left child (node, right, left). Take two nodes at the same depth. Their paths from the root split at some lowest common ancestor; one lies in that ancestor’s right subtree and the other in its left subtree. Since the right subtree is explored completely before the left subtree, the node further to the right is always visited first. So the first node seen at each depth is the rightmost one. For the left view, the same argument works with the usual node, left, right order.

How do we know a depth is new? Keep the answer list and compare the current depth with its size. When we reach a node at depth d, all of its ancestors (at depths 0 to d - 1) were visited earlier, and each of those depths already has an entry, so the list has at least d entries. It has exactly d entries if and only if no node at depth d has been seen yet. That single comparison, depth == out.size(), replaces a set of seen depths.

Algorithm.

  1. Call viewDfs(root, 0).
  2. In viewDfs(node, depth): if node is null, return. If depth == out.size(), append the node’s value.
  3. Recurse into the child on the viewed side first, then the other child, both with depth + 1.
static List<Integer> rightViewDfs(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    viewDfs(root, 0, out, true);
    return out;
}

static List<Integer> leftViewDfs(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    viewDfs(root, 0, out, false);
    return out;
}

static void viewDfs(TreeNode node, int depth, List<Integer> out, boolean rightSide) {
    if (node == null) return;
    if (depth == out.size()) out.add(node.val);          // first node ever reached at this depth
    TreeNode near = rightSide ? node.right : node.left;   // the side we look from goes first
    TreeNode far = rightSide ? node.left : node.right;
    viewDfs(near, depth + 1, out, rightSide);
    viewDfs(far, depth + 1, out, rightSide);
}

Dry run of the right view on Example 1:

visit depth out.size() before recorded? out after
1 0 0 yes [1]
3 1 1 yes [1, 3]
4 2 2 yes [1, 3, 4]
2 1 3 no [1, 3, 4]
5 2 3 no [1, 3, 4]

Complexity. Time O(n): every node is visited once. Space O(h) for the recursion, where h is the height.

Which one to use? The two approaches trade width against height. A balanced tree is wide (w about n / 2) but short (h about log n), so the DFS uses far less memory. A long chain is the reverse: the BFS queue never holds more than one node, while the DFS recursion goes n levels deep. In interviews both are accepted; the BFS is often easier to explain, and the DFS is shorter and shows a nice invariant.

Edge cases and pitfalls