Binary Tree to DLL
A hard BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 2
- Core for
- 2 roles
The problem
Reshape a binary tree into a doubly linked list without creating new nodes. Reuse each node's left link as the backward link and its right link as the forward link, arranging the nodes in inorder, and return the first node of the list.
Example 1
- Input
- [4,2,5,1,3]
- Output
- DLL: 1<->2<->3<->4<->5
- Why
- Inorder traversal of the tree is 1,2,3,4,5, which becomes the doubly linked list order.
Example 2
- Input
- [1]
- Output
- DLL: 1
- Why
- A single node becomes a DLL of length 1.
Example 3
- Input
- [1,2]
- Output
- DLL: 2<->1
- Why
- Inorder of tree [1,2] (where 2 is left child) is 2,1. The DLL follows this order.
Constraints
- The number of nodes is in the range [0, 1000].
- -1000 <= Node.val <= 1000
How to think about it
Updated 2026-09-29Converting a tree to a doubly linked list in inorder sequence does not require allocating new nodes. An inorder traversal visits nodes one by one; maintaining a pointer to the previously visited node lets you re-wire `prev.right = curr` and `curr.left = prev` on the fly, repurposing existing tree pointers directly.
Approaches, worst first
Inorder list buffer and pointer rewire
time O(n) · space O(n)
Traverse the tree to store all nodes in a flat list in inorder order, then iterate over the list updating each node's left and right pointers. Simple to implement, but uses O(n) auxiliary list memory.
In-place recursive inorder stitchingWrite this one
time O(n) · space O(h)
Perform standard inorder traversal with a persistent `prev` pointer. At each step, link `prev.right = curr` and `curr.left = prev`, then advance `prev = curr`. Memory is restricted purely to the recursion call stack.
Where people lose marks · 2
- Handling the head pointer: the head of the DLL is the very first node visited (leftmost leaf), which must be captured when `prev` is still null.
- Empty tree input: if `root == null`, returning null immediately prevents null pointer exceptions when attempting to access tree nodes.
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Asked at
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .