DSA sheet · Trees · BFS (level order) pattern

Left View & Right View of a Binary Tree

Two problems in one video, because they differ by a single line. The teacher shows that a "view" is really a level order question: the left view is the first node of every level, and the right view is the last node of every level. She starts from the brute force (store every level, then pick one value), then saves the space by picking the right node while the level is being popped. The prerequisite is plain level order traversal.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Left view, brute force: store levels, take the first of each
• Part B · Left view, optimal BFS: keep only index 0
• Part C · Right view with BFS: keep only index size − 1
• Part D · Revision page

Part 0 · Before starting

The tree node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Words we need

• Level: a row of the tree. Root = level 0, its children = level 1, and so on.
• View: imagine standing beside the tree and looking at it from one side. On each level you can only see the one node nearest to you. Every other node on that level is hidden behind it.
• Level order traversal: BFS with a queue. At the start of each round, size = len(queue) is the number of nodes on the current level, and the inner loop pops exactly those. Inside that loop, the loop counter i tells us the node's position in its level: 0 for the leftmost, size − 1 for the rightmost.

from collections import deque

def level_order(root):
    ans = []
    if root is None:
        return ans
    queue = deque([root])
    while queue:
        size = len(queue)
        level = []
        for i in range(size):              # i = position inside the level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        ans.append(level)
    return ans

Part A · Left view, brute force

GFG · Left View of Binary Tree

1The question in simple words

Given the root of a binary tree, return the values you would see if you stood on the left side of the tree, from top to bottom. This is the teacher's tree, which we use for the whole page:

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

• Level 0: only 1, so you see it.
• Level 1: 2 is in front; 3 is hidden behind it.
• Level 2: 7 is in front; 4 and 5 are behind it.
• Level 3: 6 is in front. It's far away on the right side of the drawing, but nothing on level 3 is further left, so you see it.

Left view: [1, 2, 7, 6].

2What the constraints tell us

• Number of nodes: 0 to 10⁵ → the tree can be empty → base case needed: if the root is None, return an empty list.
• n up to 10⁵ → an O(n²) idea would be 10¹⁰ operations. The teacher's rule: beyond about 10⁸ is unsafe, and 10⁹–10¹⁰ will surely TLE. So we need O(n).

3Intuition

Write down the plain level order for the tree:

The first column of values is exactly [1, 2, 7, 6]. The left view = the first element of every level. So if you know level order, this problem is almost done.

4Building the logic

1. Get all rows with plain level order.
2. Go through the rows and take row[0] from each one.

Why this is brute force

Only one value per level matters, yet we stored every value of every level (O(n) extra space) just to throw most of them away. Part B avoids storing them.

5Approach steps

1. If the root is None, return [].
2. Do level order and collect each row.
3. Return the first value of each row.

6Code (Python)

from collections import deque

def left_view_brute(root):
    if root is None:
        return []
    rows = []
    queue = deque([root])
    while queue:
        size = len(queue)
        level = []
        for i in range(size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        rows.append(level)
    return [row[0] for row in rows]        # first of every level

7Code line by line

8Dry run

1. Level order gives [[1], [2, 3], [7, 4, 5], [6, 7]].
2. Firsts: 1, 2, 7, 6 → [1, 2, 7, 6].

9Complexity & remember

• Time O(n).
• Space O(n) for the queue plus O(n) for all the stored rows.

Part B · Left view, optimal BFS

1The question, and 2 the constraints

Same question and constraints as Part A: 0 nodes allowed (keep the empty check), up to 10⁵ nodes (O(n) needed).

3Intuition: pick the node while popping

We don't need the rows at all. Inside the inner loop, i already tells us each node's position in its level. When i == 0, the node we just popped is the first of its level, so we add its value to the answer right then. All other nodes are popped but not stored.

4Building the logic: edit the level order code

• level = [] → removed. We don't create sublists any more.
• level.append(node.val) → replaced by if i == 0: ans.append(node.val). Note we add the value, not the node.
• ans.append(level) after the for loop → removed. After a level ends there's nothing left to do; the first node was already saved.
• Pushing children → kept exactly the same, for every node.

        1
       / \
      2   3
         / \
        4   5       ← now 4 is the first node of level 2

5Approach steps

1. If the root is None, return [].
2. Put the root in the queue.
3. While the queue isn't empty: size = len(queue).
4. For i from 0 to size − 1: pop a node; if i == 0, add its value to the answer; push its left and right children if they exist.
5. Return the answer.

6Code (Python)

from collections import deque

def left_view(root):
    ans = []
    if root is None:                       # 0 nodes allowed
        return ans
    queue = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == 0:                     # first node of this level
                ans.append(node.val)
            if node.left:                  # children of EVERY node
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return ans

On GFG the method is usually called LeftView(root) inside a class; the body is the same.

7Code line by line

8Dry run on the teacher's tree

Yellow = the node at i == 0, which goes into the answer.

9Complexity & remember

• Time: exactly O(n), because every node is popped once, and each pop does O(1) work.
• Space O(n) worst case for the queue. The teacher's picture: in a full binary tree, the queue grows to 1, then 2, then 3, then 4… and peaks at the whole last level, which holds about n/2 nodes. n/2 is still linear.
• What we saved compared to Part A: all the stored rows. The answer itself is just one value per level.

         1
       /   \
      2     3
     / \   / \
    7   8 4   5     ← all 4 sit in the queue together (≈ n/2)

Part C · Right view with BFS

LeetCode 199 · Binary Tree Right Side View

1The question in simple words

Now stand on the right side and list what you see, top to bottom. Same tree:

           1           ← see 1
         /   \
        2     3        ← see 3 (2 is behind it)
       /     / \
      7     4   5      ← see 5 (7 and 4 are behind)
           /     \
          6       7    ← see 7 (6 is behind)

Right view: [1, 3, 5, 7]. In the level order rows [[1], [2, 3], [7, 4, 5], [6, 7]], these are the last values of each row.

2What the constraints tell us

• Up to 10⁵ nodes in the version she reads → we already have an O(n) method, so it will pass.
• The version on screen says at least one node, so by the teacher's rule the BFS doesn't need an empty check.

3Intuition

In a level of length size, positions run from 0 to size − 1 (zero-based). Level 0 has 1 node, so its last position is 1 − 1 = 0. Level 1 has 2 nodes, so its last position is 2 − 1 = 1. The right view = the node at position size − 1 in every level.

4Building the logic: change one line

Take the left view code. The only change is the condition:

The teacher literally copies her left view code into the right view problem and changes 0 to size - 1.

5Approach steps

1. If the root is None, return [].
2. BFS by levels with size = len(queue).
3. For each popped node, if i == size - 1, add its value to the answer.
4. Push the children of every node (left, then right).
5. Return the answer.

6Code (Python)

from collections import deque

class Solution:
    def rightSideView(self, root):
        ans = []
        if root is None:                   # LeetCode allows 0 nodes
            return ans
        queue = deque([root])
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i == size - 1:          # last node of this level
                    ans.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans

7Code line by line

8Dry run on the teacher's tree

Yellow = the node at i == size − 1.

9Complexity & remember

• Time O(n): each node popped once.
• Space O(n) worst case: the queue holds the widest level (about n/2 in a full tree).

Part D · Revision page

Extra (not in the video): the DFS idea

The teacher mentions trying both BFS and DFS when possible, but this video only codes BFS. For completeness: DFS can do it by carrying the level, and adding a node the first time a level is reached (level == len(ans)). Calling left first means the first node reached on each level is the leftmost one (left view). Calling right first gives the right view.

class Solution:
    def rightSideView(self, root):
        ans = []
        self.dfs(root, 0, ans)
        return ans

    def dfs(self, root, level, ans):
        if root is None:
            return
        if level == len(ans):              # first node seen on this level
            ans.append(root.val)
        self.dfs(root.right, level + 1, ans)   # right first
        self.dfs(root.left, level + 1, ans)

Swap the two recursive calls (left first) and it becomes the left view.

root = TreeNode(1,
         TreeNode(2, TreeNode(7)),
         TreeNode(3, TreeNode(4, TreeNode(6)), TreeNode(5, None, TreeNode(7))))
small = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))

print(left_view(root))                     # [1, 2, 7, 6]
print(Solution().rightSideView(root))      # [1, 3, 5, 7]
print(Solution().rightSideView(small))     # [1, 3, 4]
print(left_view(None))                     # []

Based on this video: Left View & Right View of Binary Tree | BFS