DSA sheet · Trees · Binary search tree pattern

Binary Tree to Doubly Linked List

This is the last problem of the pattern. We take a binary tree and, without creating any new nodes, rewire it into a doubly linked list in inorder order. Each node's left pointer becomes "previous" and its right pointer becomes "next". The teacher first solves it the easy way: store the inorder nodes in a list, then link neighbours. Then she removes the list using an idea that keeps coming back in tree problems: decide what to do with each node at the moment you visit it, using a prev pointer.

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 inorder, then link
• Part B · Optimal: link while doing the inorder (prev + head)
• Part C · Revision page

Part 0 · Before starting

Doubly linked list (DLL)

A chain where every box has two pointers: prev (the box before it) and next (the box after it). The first box's prev is None and the last box's next is None. The first box is called the head. We return the head, because from it you can reach every other box.

Same node, new meaning for its pointers

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left     # will become "prev"
        self.right = right   # will become "next"

Inorder traversal (recap)

Inorder = left subtree, then the node, then the right subtree. The DLL must list the nodes in exactly this order.

Part A · Brute force: store the inorder, then link

GFG "Binary Tree to DLL"

1The question in simple words

Given the root of a binary tree, turn it in place into a doubly linked list:

• The node order is the inorder order.
• left = previous node, right = next node.
• The first inorder node is the head. Return it.

    1
   / \
  2   3

None ← 2 ⇄ 1 ⇄ 3 → None

Inorder is 2, 1, 3. So 2's prev is None and its next is 1. 1's prev is 2 and its next is 3. 3's next is None.

        10
       /  \
     20    30
    /  \
  40    60

None ← 40 ⇄ 20 ⇄ 60 ⇄ 10 ⇄ 30 → None
       head

2What the constraints tell us

• Nodes: 1 to 10⁶ → the tree is never empty, so there is always a head to return.
• 10⁶ is big. An O(n²) solution would be 10¹² steps. The teacher repeats the rule from her complexity video: past about 10⁸ you risk TLE, and at 10⁹ you get it for sure. So only a linear solution will do.
• Values: 0 to 10⁵. They fit in an int, and we never do any maths on them, so no worries there.

3Intuition: get the order first, then tie neighbours

The question literally says "inorder". So the first idea: do an inorder traversal, store the nodes in a list, then connect each node to its neighbours in the list.

4Building the conditions

For the node at index i:

• prev is the node at i − 1 → nodes[i].left = nodes[i-1].
• next is the node at i + 1 → nodes[i].right = nodes[i+1].

The edges need care:

• i = 0 (the first node): there is no i − 1. So only set its next. Only do the "prev" step when i > 0.
• i = last: there is no i + 1. So only set its prev. Only do the "next" step when i < n − 1.
• Every middle node gets both.

Example: in the tree, 10's left child was 20 and its right child was 30. In the DLL, 10's left must become 60 (the node before it in inorder) and its right stays 30.

5Approach steps

1. Inorder traversal, appending each node to nodes.
2. For each i: if i > 0, left = nodes[i-1]. If i < n−1, right = nodes[i+1].
3. Return nodes[0].

6Code (Python)

class Solution:
    def bToDLL(self, root):
        nodes = []
        self.inorder(root, nodes)
        if not nodes:                        # not needed (n >= 1), just safe
            return None
        n = len(nodes)
        for i in range(n):
            if i > 0:
                nodes[i].left = nodes[i - 1]     # prev
            if i < n - 1:
                nodes[i].right = nodes[i + 1]    # next
        return nodes[0]                      # head

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

7Code line by line

8Dry run

1. i = 0 (40): no prev. 40.right = 20.
2. i = 1 (20): 20.left = 40, 20.right = 60 (it was already 60 in the tree).
3. i = 2 (60): 60.left = 20, 60.right = 10.
4. i = 3 (10): 10.left = 60 (it used to be 20), 10.right = 30.
5. i = 4 (30): 30.left = 10. It's the last node, so no next.
6. Return 40. Walking right: 40 → 20 → 60 → 10 → 30 ✓. Walking left from 30: 30 → 10 → 60 → 20 → 40 ✓

9Complexity & remember

• Time O(n) + O(n): one pass for the inorder, one for linking. Still linear, so it passes for 10⁶.
• Space O(n) for the list, plus O(height) for the recursion (log n balanced, n skewed).

It works, but the interviewer won't like the extra O(n) list. Next we get rid of it.

Part B · Optimal: link while doing the inorder (prev + head)

1The question (same as Part A)

Same input and output. New goal: no extra list.

2What the constraints tell us

• Same as Part A: at least 1 node, and we must stay linear.
• We'll still use recursion, so the call stack costs O(height). But the O(n) list is gone.

3Intuition: remember the last node you visited

If we can't store all the nodes, we must decide at the moment we visit a node. In an inorder traversal, the node visited just before the current one is exactly its previous node in the DLL. So we only need to remember one node: the last one we visited. Call it prev.

When we visit root:

• If prev is None, this is the very first inorder node → it is the head.
• Otherwise, tie the two together: prev.right = root (prev's next) and root.left = prev (root's prev).
• Then prev = root, because root is now the last visited node.

4Building the logic step by step

Where does the work go? In the middle of inorder

Inorder code is: go left, visit, go right. When we stored values, the "visit" line was nodes.append(...). Now we put the linking logic there instead. At that moment we hold the current node (root), and prev holds the one before it.

Finding the head

From 10 we go left to 20, then left to 40, then left to None, which returns. We're back at 40. This is the first node that reaches the "visit" line. At that moment prev is still None (nothing visited yet). So: prev is None ⇒ head = root. Every later visit will find prev not None, so the head is set only once.

Updating prev, always

After 40 is visited, we go up to 20. If we forgot to update prev, 20 would also see "prev is None" and wrongly become the head. So after the if/else, always set prev = root, and do it before going right.

Why prev must be shared by all calls (the most important point)

After 60 is visited, prev = 60. Then 60's call ends, 20's call ends, and we're back at 10. Many students expect prev to "go back" to 20 here. It must not. The node just before 10 in inorder is 60. Because prev is one variable shared by all calls (a global or class variable, self.prev in Python), it still holds 60 when we reach 10, which is exactly right. So 60.right = 10 and 10.left = 60.

What do we return?

The recursion itself returns nothing useful. It just links nodes. The answer is the head we saved at the first visit, so the main function returns self.head.

5Approach steps

1. prev = None, head = None (shared by all calls).
2. inorder(root): if root is None → return.
3. inorder(root.left).
4. If prev is None → head = root. Else → prev.right = root, root.left = prev.
5. prev = root.
6. inorder(root.right).
7. Return head.

6Code (Python)

class Solution:
    def bToDLL(self, root):
        self.prev = None        # last node visited in inorder
        self.head = None        # first node visited in inorder
        self.inorder(root)
        return self.head

    def inorder(self, root):
        if root is None:
            return
        self.inorder(root.left)             # 1. finish the left side
        if self.prev is None:               # 2. first node ever -> head
            self.head = root
        else:                               #    otherwise link prev ⇄ root
            self.prev.right = root
            root.left = self.prev
        self.prev = root                    # 3. root is now the last visited
        self.inorder(root.right)            # 4. then the right side

7Code line by line

8Dry run using the call stack

Tree: 10 (20 (40, 60), 30). io(x) = inorder(x).

1. io(10) → io(20) → io(40) → io(None) returns.
2. Visit 40: prev is None → head = 40. prev = 40. io(40.right = None) returns. io(40) ends.
3. Visit 20: prev = 40 → 40.right = 20, 20.left = 40. prev = 20. Go right: io(60).
4. io(60) → left is None. Visit 60: prev = 20 → 20.right = 60, 60.left = 20. prev = 60. Right is None. io(60) ends, then io(20) ends.
5. Visit 10: prev is still 60 (shared) → 60.right = 10, 10.left = 60. prev = 10. Go right: io(30).
6. io(30) → left None. Visit 30: prev = 10 → 10.right = 30, 30.left = 10. prev = 30. Right None. Everything returns.
7. Return head = 40. DLL: 40 ⇄ 20 ⇄ 60 ⇄ 10 ⇄ 30 ✓

9Complexity & remember

• Time O(n): every node is visited once, in a single pass. The brute force needed two passes.
• Space O(height): only the recursion stack. That's log n for a balanced tree and n for a skewed one. No extra list.

The teacher notes that both versions are acceptable, but this one is a little faster (one pass) and lighter on memory, because we rewire the same tree while walking it.

Part C · Revision page

root = TreeNode(10, TreeNode(20, TreeNode(40), TreeNode(60)), TreeNode(30))
head = Solution().bToDLL(root)

fwd, node, last = [], head, None
while node:
    fwd.append(node.val)
    last, node = node, node.right
back, node = [], last
while node:
    back.append(node.val)
    node = node.left
print(fwd)    # [40, 20, 60, 10, 30]
print(back)   # [30, 10, 60, 20, 40]

Based on this video: Convert Binary Tree to Doubly Linked List