Convert a binary tree to a doubly linked list (in-order)

Medium

Problem

Convert the tree into a doubly linked list in place, using left as prev and right as next, so that the list follows the in-order sequence. Return the head.

Example 1

Input:  10 with left 12 (children 25, 30) and right 15 (left 36)
Output: 25 ⇄ 12 ⇄ 30 ⇄ 10 ⇄ 36 ⇄ 15

Also asked as: Convert Binary tree into Doubly Linked List

Test cases

Case 1

Input:    [10,12,15,25,30,36]
Expected: [25,12,30,10,36,15]

Case 2

Input:    [2,1,3]
Expected: [1,2,3]

Case 3

Input:    [1]
Expected: [1]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. In-order traversal, stitch prev ↔ current

Time O(n)Space O(h)

Do an in-order walk keeping a `prev` pointer; set prev.right = cur and cur.left = prev. The first visited node is the DLL head.

function treeToDLL(root) {
let head = null, prev = null;
const inorder = (n) => {
if (!n) return;
inorder(n.left);
if (prev) { prev.right = n; n.left = prev; }
else head = n;
prev = n;
inorder(n.right);
};
inorder(root);
return head;
}