Pattern visualizer
Binary Tree to DLL
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. 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)..
Inorder traversal stitching left <-> prev, right <-> next
Convert the tree to a DLL by inorder traversal, rewiring left <- prev and right <- next as each node is visited. prev starts null.
1FUNCTION inorder(node):2 IF node = null: RETURN3 inorder(node.left)4 IF prev = null:5 head <- node6 ELSE:7 prev.right <- node8 node.left <- prev9 prev <- node10 inorder(node.right)11inorder(root)12RETURN head
← / → step · space play · Home restart