Binary Tree to DLL

Inorder traversal stitching left <-> prev, right <-> next

time O(n)space O(h) recursion stack

Inorder traversal already visits nodes in the exact order the DLL needs. The only new idea is to remember the LAST node visited (prev): the moment the current node is reached, prev is already its correct DLL predecessor, so prev.right <- curr and curr.left <- prev links them immediately, reusing the tree's own pointers instead of allocating new ones. The very first node visited has no prev yet, so it becomes the head.

Details

Animated on: Given the root of a binary tree, convert it in-place to a doubly linked list in inorder order — the left pointer becomes 'prev' and the right pointer becomes 'next' — for the tree [4, 2, 5, 1, 3] (root 4, left 2 with children 1 and 3, right 5).

Problem:Binary Tree to DLLHard

Inorder traversal stitching left <-> prev, right <-> next

step 1 / 11

Convert the tree to a DLL by inorder traversal, rewiring left <- prev and right <- next as each node is visited. prev starts null.

Pseudocode

1FUNCTION inorder(node):
2  IF node = null: RETURN
3  inorder(node.left)
4  IF prev = null:
5    head <- node
6  ELSE:
7    prev.right <- node
8    node.left <- prev
9  prev <- node
10  inorder(node.right)
11inorder(root)
12RETURN head

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Convert the tree to a DLL by inorder traversal, rewiring left <- prev and right <- next as each node is visited. prev starts null.
Enter inorder(4). It has a left child, so recurse there first — the whole left subtree must be linked before 4 can join the list.
Enter inorder(2). It has a left child, so recurse there first — the whole left subtree must be linked before 2 can join the list.
1 is the first node inorder finds — no predecessor exists yet, so 1 becomes the head of the DLL.
Stitch: prev(1).right <- 2 and 2.left <- 1. 1 and 2 are now doubly linked.
2 is linked in. Now recurse into its right subtree.
Stitch: prev(2).right <- 3 and 3.left <- 2. 2 and 3 are now doubly linked.
Stitch: prev(3).right <- 4 and 4.left <- 3. 3 and 4 are now doubly linked.
4 is linked in. Now recurse into its right subtree.
Stitch: prev(4).right <- 5 and 5.left <- 4. 4 and 5 are now doubly linked.
Traversal finished. head = 1, and every node is doubly linked in inorder sequence — no extra memory beyond the recursion stack was used.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree to DLL in the editor All BST problems Back to roadmap