DSA sheet · Trees · Construction / serialization pattern

Flatten Binary Tree to Linked List

This is the first problem where we change the shape of the tree itself instead of only reading it. That is why the sheet puts it in the "construction" pattern. The teacher first spots that the answer is just the preorder order of the nodes, and solves it the easy way with a list (brute force). Then she removes the list and the recursion completely, and solves it with O(1) extra space using a Morris-style walk. That second idea is new and very popular in interviews, so we go through it slowly.

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 · Brute force: store the preorder, then relink
• Part B · Optimal: Morris-style flattening, O(1) space
• Part C · Revision page

Part 0 · Before starting

What is a linked list?

A linked list is a chain of boxes. Each box holds a value and a pointer to the next box. The last box points to nothing (None). Here we don't get a separate linked-list class. We must build the chain out of the tree nodes, using the right pointer as "next".

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left     # must become None everywhere
        self.right = right   # will act as the "next" pointer

Preorder traversal (recap)

Preorder means: visit the root first, then the whole left subtree, then the whole right subtree. (A subtree is a node together with everything below it.) The same rule is used again inside every subtree.

def preorder(node):
    if node is None:
        return
    print(node.val)          # root
    preorder(node.left)      # then left
    preorder(node.right)     # then right

Words used on this page

• In place: we must reuse the same node objects and only change their pointers. Making new nodes is not allowed.
• Leaf: a node with no children (left and right are both None).
• Rightmost node of a subtree: start at the subtree's top and keep going .right until there is no right child. The node where you stop is the rightmost one.

Part A · Brute force: store the preorder, then relink

LeetCode 114

1The question in simple words

You get the root of a binary tree. Turn it into a "linked list" that hangs only to the right:

• Every node's left must become None.
• Every node's right must point to the node that comes next.
• The order of the nodes must be the preorder order.
• Return nothing. Change the tree that was given to you.

        1
       / \
      2   5
     / \   \
    3   4   6

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

2What the constraints tell us

• Number of nodes: 0 to 2000 → 0 is allowed, so the root can be None. The code must not crash on an empty tree.
• Values: −100 to 100. The teacher reads this to see if we need a bigger number type. Ints hold values up to about 10⁹, and we never add or multiply values here. We only move pointers. So the values never matter.
• n ≤ 2000 is small. Even a slow solution would pass. The real challenge in this problem is space, not time.

3Intuition: the answer is the preorder

Read the flattened chain from top to bottom: 1, 2, 3, 4, 5, 6. Now do a preorder of the input tree:

• Root first → 1.
• Then its left subtree. Its root is 2, then 2's left → 3, then 2's right → 4.
• Then 1's right subtree. Its root is 5. 5 has no left, so we write nothing. Then 5's right → 6.

Preorder = 1 2 3 4 5 6, exactly the chain. So the first idea is: collect the nodes in preorder, then tie each node to the next one.

4Building the logic

Rule: rearrange, don't rebuild

The teacher stresses this. It is tempting to make new nodes 1 → 2 → 3 … and return them. That is not allowed. The tree's structure stays the same (each node still has a value, a left and a right). We are only allowed to re-point the existing nodes.

Rule: for every position i, set right to the next node and left to None

Say the list is nodes = [1, 2, 3, 4, 5, 6] (the real node objects). Look at index i:

• nodes[i].right = nodes[i + 1]: the next node in preorder goes to its right.
• nodes[i].left = None: the left side must be empty. Node 1 still has 2 on its left, so we must clear it. Otherwise the tree would have 2 hanging on both sides of 1.

Watch it happen:

• i = 0 (node 1): 1.right = 2, 1.left = None. Now 1 has only 2 below it (2 still holds 3 and 4).
• i = 1 (node 2): 2.right = 3, 2.left = None.
• i = 2 (node 3): 3.right = 4. 3.left was already None.
• i = 3 (node 4): 4.right = 5. Since 5 still holds 6, both come along.
• i = 4 (node 5): 5.right = 6 (already true), 5.left = None (already true).

Rule: stop at the second-last node

The loop uses i + 1. At the last index there is no i + 1, so we'd go out of range. We also don't need to touch the last node at all.

5Approach steps

1. Make an empty list nodes.
2. Do a preorder traversal and append each node (not its value).
3. For i from 0 to the second-last index: nodes[i].left = None, nodes[i].right = nodes[i+1].
4. Return nothing (the tree has been changed in place).

6Code (Python)

class Solution:
    def flatten(self, root):
        nodes = []
        self.preorder(root, nodes)           # 1. save nodes in preorder
        for i in range(len(nodes) - 1):      # 2. up to the second-last
            nodes[i].left = None
            nodes[i].right = nodes[i + 1]

    def preorder(self, node, nodes):
        if node is None:
            return
        nodes.append(node)                   # root
        self.preorder(node.left, nodes)      # left
        self.preorder(node.right, nodes)     # right

7Code line by line

8Dry run

Tree from step 1. First the preorder fills the list:

1. i = 0: 1.left = None (2 is removed from the left), 1.right = 2. The old right part (5 → 6) is no longer reachable from 1, but it is safe, because it's stored in the list.
2. i = 1: 2.left = None (3 leaves the left), 2.right = 3.
3. i = 2: 3.left = None, 3.right = 4.
4. i = 3: 4.left = None, 4.right = 5. Now 5 → 6 is attached again.
5. i = 4: 5.left = None, 5.right = 6.
6. The loop stops (i = 5 would need index 6). 6 is a leaf, already fine. The chain is 1 → 2 → 3 → 4 → 5 → 6 ✓

The stack is only as tall as the path from the root, which is why the recursion costs O(height).

9Complexity & remember

• Time O(n) + O(n) = O(2n) = O(n): one pass for the preorder, one pass over the list.
• Space O(n) for the list, plus O(height) for the recursion stack (log n if balanced, n if skewed).

It works and every student should be able to write it. But it is not optimised, because of the extra list and the call stack. An interviewer will ask: "can you do it without extra space?"

Part B · Optimal: Morris-style flattening, O(1) space

1The question (same as Part A)

Same input, same output. The new goal: no list, no recursion, only a few pointer variables.

2What the constraints tell us

• Same as before. 0 nodes is allowed. Our loop is while curr:, so for an empty tree it simply never runs. No special check is needed.
• The goal is now O(1) space, so recursion (O(height) stack) is also not allowed. We'll use a while loop.

3Intuition: lift the left side over to the right

The teacher calls this the Morris traversal idea. If you've never seen it, that's normal. You learn it once and then it feels easy. (She jokes that only geniuses invent it on the spot.)

Stand at a node. In the final answer, everything must be on the right. So:

1. Pick up the node's whole left subtree and put it on the right.
2. The old right subtree must not be lost. Hang it under the rightmost node of the subtree you just moved.
3. Step down to the right and repeat.

Why the rightmost node? In preorder, the old right subtree comes right after the last node of the left subtree. The last node of a subtree in preorder is found by going right, right, right… as far as possible. So that's where the right subtree belongs.

4Building the logic step by step (her derivation)

Step 1: save the right side before overwriting it

At node 1, we want 1.right = 1.left. But if we write that line first, the old right subtree (5 → 6) is gone, because nothing points to it any more. So first copy it into a temporary variable:

After these 3 lines the tree looks like this, with 5 → 6 waiting in temp:

1
 \
  2
 / \
3   4

5
 \
  6

Step 2: find where to re-attach temp

Should 5 → 6 go under 3 or under 4? Preorder of the moved part is 2, 3, 4, so 5 must come after 4. And 4 is the rightmost node of the subtree starting at 2 (2 → right → 4, and 4 has no right). So we write a small helper:

def rightMost(self, node):
    while node.right is not None:   # stop at the node with NO right child
        node = node.right
    return node

We call it with curr.right (that's 2, the top of the moved subtree). It checks: does 2 have a right? Yes → move to 4. Does 4 have a right? No → return 4.

Step 3: attach temp to the rightmost node's RIGHT

rm.right = temp. Then 4 → 5 → 6. We only connect 5; 6 comes along because it is already linked to 5. Now temp has done its job and is free to be reused at the next node.

Step 4: move down and repeat, so wrap it in a loop

After one round, only the part at node 1 is correct. The next node to fix is curr.right (node 2). So curr = curr.right, inside while curr:, until we fall off the end.

At node 2: temp = 4 → 5 → 6. 2.right = 3, 2.left = None. rightMost(3) = 3 (3 has no right). 3.right = temp. Now the chain is 1 → 2 → 3 → 4 → 5 → 6. It looks finished, but the code can't know that until curr has visited every node.

Step 5: skip all that work when there is no left child

At node 3 the teacher notices: 3's left is already None. Saving temp, moving None to the right and searching the rightmost node makes no sense. So all four lines go inside if curr.left:.

5Approach steps

1. curr = root.
2. While curr is not None:
3. If curr.left exists: save temp = curr.right, move the left subtree to the right, set left to None, find the rightmost node of the moved subtree, hang temp on its right.
4. In all cases, curr = curr.right.
5. Return nothing.

6Code (Python)

class Solution:
    def flatten(self, root):
        curr = root
        while curr:
            if curr.left:                        # only if there is a left part to move
                temp = curr.right                # 1. save the right side
                curr.right = curr.left           # 2. move left subtree to the right
                curr.left = None                 # 3. clear the left
                rm = self.rightMost(curr.right)  # 4. end of the moved part
                rm.right = temp                  # 5. re-attach the old right side
            curr = curr.right                    # always step forward

    def rightMost(self, node):
        while node.right:
            node = node.right
        return node

7Code line by line

8Dry run

Same tree as Part A: 1 (2 (3, 4), 5 (–, 6)).

1. curr = 1, left = 2 exists. temp = 5→6. 1.right = 2, 1.left = None. rightMost(2): 2 has right 4 → move; 4 has no right → return 4. 4.right = 5→6.
2. curr = 2 (1.right). left = 3 exists. temp = 4→5→6. 2.right = 3, 2.left = None. rightMost(3): 3 has no right → return 3. 3.right = 4→5→6.
3. curr = 3: left is None → skip the if. curr = 4.
4. curr = 4: no left → curr = 5.
5. curr = 5: no left → curr = 6.
6. curr = 6: no left → curr = None. The loop ends. Chain: 1 → 2 → 3 → 4 → 5 → 6 ✓

1
 \
  2
 / \
3   4
     \
      5
       \
        6

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

9Complexity & remember

Time: it looks like O(n log n), but it is O(2n)

The outer loop visits every node once → O(n). Inside, rightMost walks down a right edge, which looks like up to log n more steps per node, so you might guess O(n log n). The teacher says that is too pessimistic. Count how many times each node is touched:

So in the worst case each node is touched at most twice: once by curr, and once while searching for a rightmost node. That gives O(2n) = O(n).

• Space O(1): no list, no recursion. Only curr, temp and rm. This is the most optimised version.
• We return nothing. We changed the given tree's structure, and that's exactly why the sheet lists it under the construction pattern.

Part C · Revision page

class Solution:
    def flatten(self, root):
        self.prev = None
        self.build(root)

    def build(self, node):
        if node is None:
            return
        self.build(node.right)      # right first...
        self.build(node.left)       # ...then left
        node.right = self.prev      # the node handled just before is "next"
        node.left = None
        self.prev = node

root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)),
                   TreeNode(5, None, TreeNode(6)))
Solution().flatten(root)

out, node = [], root
while node:
    assert node.left is None     # every left must be empty
    out.append(node.val)
    node = node.right
print(out)                       # [1, 2, 3, 4, 5, 6]

Based on this video: Flatten Binary Tree to Linked List