Convert a binary tree to a doubly linked list (in-order)
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: []
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;}