DSA sheet · Trees · BFS pattern (also solved with DFS)

Populating Next Right Pointers

Here every node gets one extra pointer called next, and we have to point it at the node just to its right on the same level. The picture screams "levels", so the teacher solves it first with BFS (level order traversal), which she calls both the easier and the best approach. Then she asks: can DFS do it too? It can, with one clever idea: connect a level while standing one level above it. That idea, "the parent wires up its children", shows up again in many tree problems.

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

• Part 0 · Perfect binary tree & the Node class
• Part A · Next pointers with BFS
• Part B · Next pointers with DFS
• Part C · Revision page

Part 0 · Perfect binary tree & the Node class

Perfect binary tree

A perfect binary tree is the "fullest" kind of tree:

• every node that isn't a leaf has exactly two children (never just one), and
• all the leaves (nodes with no children) are on the same level.

A level is a row of the tree: the root is level 0, its children are level 1, and so on. In a perfect tree, level k has exactly 2^k nodes: 1, 2, 4, 8…

This promise is very useful later: if a node has a left child, it surely has a right child too, and if it has no left child, it is a leaf.

The Node class

class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next     # starts as None for every node

So each node has four things: a value, a left pointer, a right pointer, and the new next pointer.

Part A · Next pointers with BFS

LeetCode 116

1The question in simple words

You get a perfect binary tree. At the start, every next is None. Make each node's next point to the node right after it on the same level. The last node of each level has nobody to its right, so its next stays None.

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

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

• The root is alone on its level, so we touch nothing there.
• 2 → 3. 3 is last on its level, so it stays None.
• 4 → 5 → 6 → 7. Note 5 → 6, even though 5 and 6 have different parents. 7 stays None.

We don't build anything new. We only fill the pointers in place. (LeetCode still wants the root returned at the end, so the code does return root.)

2What the constraints tell us

• Number of nodes: 0 to 2¹² − 1. 0 is allowed → we need a base case for an empty tree.
• How big is 2¹²? The teacher's quick trick: 2¹⁰ = 1024, so 2¹¹ is about 2000 and 2¹² is about 4000. So n is around 4 × 10³ → small, and an O(n) solution is easily fast enough.
• Values: −1000 to 1000. Why read this? If we had to add or multiply values, big numbers could overflow an int (in Java/C++ we'd need long). Here we never do maths on the values, we only move pointers, so this is safe.

3Intuition: which pattern does this look like?

So far we know two ways to walk a tree: DFS (go deep) and BFS (go level by level). Look at the "after" picture: the arrows run along each level. That is exactly what level order traversal sees. In BFS, after popping a node, the next node in the queue is its right-hand neighbour on the same level, as long as the current node isn't the last one of the level.

4Building the logic from the example

Which nodes should get a next?

Write the levels out: [1], [2, 3], [4, 5, 6, 7]. In every level, all nodes except the last one point to their neighbour. So we need to know each node's position inside its level.

In level-order BFS we already have it: size = number of nodes in this level, and the for loop counter i goes 0, 1, …, size − 1. So:

• i < size - 1 → not the last node → connect it.
• i == size - 1 → the last node → leave next as None.

For the root: size = 1, i = 0, and size − 1 = 0, so i is not less than 0 → nothing is connected ✓.

Where is the neighbour? Peek, don't pop

After we pop 2 from the queue, the queue's front is 3, its neighbour. So node.next = queue[0]. We only read the front (peek). We must not pop it, because 3 still needs its own turn in the loop: its own next to check, and its children to push.

Then the normal BFS part

After handling next, push the left child and the right child if they exist, exactly like normal level order traversal.

5Approach steps

1. If root is None → return None.
2. Put the root in a queue.
3. While the queue isn't empty: size = len(queue).
4. For i from 0 to size − 1: pop a node.
5. If i < size - 1 → node.next = queue[0] (peek).
6. Push its left and right children if they exist.
7. Return root.

6Code (Python)

from collections import deque

class Solution:
    def connect(self, root):
        if root is None:                 # 0 nodes is allowed
            return None
        queue = deque([root])
        while queue:
            size = len(queue)            # nodes on this level
            for i in range(size):
                node = queue.popleft()
                if i < size - 1:         # not the last node of the level
                    node.next = queue[0] # peek: the neighbour on the right
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return root

7Code line by line

8Dry run: watch the queue

Tree 1; 2, 3; 4, 5, 6, 7. Yellow = the node being popped.

9Complexity & remember

• Time O(n): every node is pushed once and popped once.
• Space O(n): the queue. At its fullest it holds the whole last level. In a perfect tree, the last level holds about n/2 nodes (just over half of all nodes), and n/2 is still linear.

The teacher's view: for a beginner this BFS version is both the easiest and the best one. Whenever a problem is about levels, BFS is usually the first thing to try.

Part B · Next pointers with DFS

1The question in simple words

Same task: fill every next. But now we walk depth first (recursion), not level by level.

2What the constraints tell us

• 0 nodes is allowed → we still need the None base case.
• Perfect tree → this matters even more here. If a node has no left child, it has no right child either, and it's a leaf. The DFS code relies on this.

3Intuition: the problem with DFS, and the fix

DFS goes 1 → 2 → 4 → … When we are standing at 2, the function holds only node 2. We have no way to reach 3 from 2: 3 is not a child of 2. So "standing at a node and connecting it to its neighbour" doesn't work in DFS.

The fix: look one level up. When we stand at 1, we can see both 2 and 3. So let the parent connect its children. In other words, we connect a level while standing on the level above it.

4Building the logic from the example

First, the idea the teacher rejects

One way that works: use DFS to collect the nodes of every level into lists (DFS level order traversal, like we did before: if this level has no list yet, make one, then add the node to it). Then go through each list and link neighbours.

class Solution:
    def connect(self, root):
        levels = []                          # levels[k] = nodes of level k
        self.collect(root, 0, levels)
        for row in levels:
            for i in range(len(row) - 1):
                row[i].next = row[i + 1]     # link neighbours in the row
        return root

    def collect(self, node, level, levels):
        if node is None:
            return
        if level == len(levels):             # first node seen on this level
            levels.append([])
        levels[level].append(node)           # store the NODE, not the value
        self.collect(node.left, level + 1, levels)
        self.collect(node.right, level + 1, levels)

Rule 1: connect a node's own two children (left → right)

Standing at 1: 1.left.next = 1.right, so 2 → 3. Standing at 2: 2.left.next = 2.right, so 4 → 5. Standing at 3: 6 → 7.

The teacher's side note: even if the right child were missing, this line would only assign None, which is harmless. In a perfect tree it is always there anyway.

Rule 2: connect the right child to the next family's left child

Rule 1 never gives us 5 → 6, because 5 and 6 have different parents. How can we reach 6 while standing at 2?

Look: 2.next is 3. That was already set earlier, when we stood at 1. And 6 is 3.left. So:

2.right.next = 2.next.left → 5.next = 3.left = 6 ✓

That's the trick: the parent's own next pointer is a bridge to the neighbouring family.

When can't we use Rule 2?

When the parent has no next, it is the last node of its level. Example: at 3, 3.next is None, so there is no family to the right, and 7 should stay None. So Rule 2 runs only if root.next exists. Without this check, root.next.left would crash on None.

The base case: root is None OR root.left is None

• root is None → empty tree, nothing to do.
• root.left is None → in a perfect tree, this means there's no right child either, so it's a leaf. A leaf has no children to connect → return. This also stops us from writing root.left.next on a None.

Why the order "connect first, then recurse" matters

Rule 2 at node 2 uses 2.next. That pointer must already be set when we arrive at 2. It is, because 1 set it before calling dfs(2). So we must do the connecting before the recursive calls (preorder: node first, then children). Every node's next is set by its parent before we ever visit it.

5Approach steps

1. connect(root) calls dfs(root) and returns root.
2. In dfs: if root is None or root.left is None → return.
3. root.left.next = root.right (same family).
4. If root.next exists → root.right.next = root.next.left (next family).
5. Recurse on root.left, then on root.right.

6Code (Python)

class Solution:
    def connect(self, root):
        self.dfs(root)
        return root

    def dfs(self, root):
        if root is None or root.left is None:   # empty, or a leaf
            return
        root.left.next = root.right             # Rule 1: my two children
        if root.next:                           # is there a family to my right?
            root.right.next = root.next.left    # Rule 2: bridge across
        self.dfs(root.left)
        self.dfs(root.right)

7Code line by line

8Dry run using the call stack

Same tree 1; 2, 3; 4, 5, 6, 7.

1. dfs(1): left exists. Rule 1: 2.next = 3. 1.next is None → skip Rule 2. Call dfs(2).
2. dfs(2): Rule 1: 4.next = 5. 2.next = 3 exists → Rule 2: 5.next = 3.left → 5.next = 6. Call dfs(4).
3. dfs(4): 4.left is None (leaf) → return. Then dfs(5) → leaf → return. dfs(2) is done.
4. Back in dfs(1), call dfs(3): Rule 1: 6.next = 7. 3.next is None → skip Rule 2, so 7 stays None ✓.
5. dfs(6), dfs(7): leaves → return. Everything unwinds. All pointers are set.

9Complexity, BFS vs DFS & remember

• Time O(n): each node is visited once.
• Space: the recursion stack. The teacher counts it as O(n), so she calls BFS and DFS equal in time and space.

BFS vs DFS, in the teacher's words, paraphrased: BFS connects a node while standing on it, because the queue already holds its neighbour. DFS can only hold one node at a time, so it has to connect each level from the level above. Both work, both are O(n) time. For level-type problems, BFS is the more natural first choice.

Side note: LeetCode's follow-up asks for O(1) extra space and says the recursion stack doesn't count. So this DFS version already satisfies it, while the BFS queue does not.

Part C · Revision page

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

root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
Solution().connect(root)
level = root
while level:                      # walk each level using next
    node, row = level, []
    while node:
        row.append(str(node.val))
        node = node.next
    print("-".join(row))         # 1, then 2-3, then 4-5-6-7
    level = level.left

Based on this video: Populating Next Right Pointers in Each Node | BFS & DFS