← Create New Paste

Flatten Binary Tree to Linked List (LeetCode 114): Three Ways to Explain It in an Interview

6 views
The problem: given the root of a binary tree, flatten it in place into a "linked list" that uses the same TreeNode objects. Every node's left pointer must become null, and its right pointer must point to the next node in preorder (root, left subtree, right subtree). It is a medium problem, but interviewers like it because there are three clean solutions with different trade-offs, and how you move between them says a lot about your understanding of tree traversal. Approach 1: collect, then relink (O(n) extra space) The most obvious answer is to run a preorder traversal, push every node into a list, and then walk the list setting node.left = None and node.right = next. It is correct and easy to verify, and it is a fine thing to say out loud first. Then say why you want better: the problem says "in place," and the list costs O(n) memory. Approach 2: reverse postorder recursion (O(h) stack) If you visit nodes in the order right subtree, left subtree, root, you see them in exactly the reverse of the final list. Keep a pointer prev to the head of the list built so far: prev = None def flatten(root): nonlocal prev if not root: return flatten(root.right) flatten(root.left) root.right = prev root.left = None prev = root Each node is attached in front of everything that should come after it. The trick is elegant, but be ready to explain why right goes before left; many candidates write it backwards and only catch it with a test case. Approach 3: Morris-style rewiring (O(1) extra space) The optimal answer avoids recursion entirely. Walk down the right spine with a pointer cur. Whenever cur has a left child, find the rightmost node of that left subtree (its preorder predecessor of cur.right). Hook cur.right onto that rightmost node, move the left subtree to cur.right, and clear cur.left. Then step cur = cur.right. cur = root while cur: if cur.left: p = cur.left while p.right: p = p.right p.right = cur.right cur.right = cur.left cur.left = None cur = cur.right Each edge is walked a constant number of times, so time stays O(n) and extra space is O(1). What to test Walk through an empty tree, a single node, a tree that is already a right-leaning chain (nothing should change), a left-only chain (everything flips to the right), and the classic example [1,2,5,3,4,null,6], which should become 1-2-3-4-5-6. Interviewers notice when you check that every left pointer is null at the end, because forgetting to clear left is the most common bug. How to talk through it A strong answer sounds like: "Preorder gives me the order. I can store it, or build it backwards with reverse postorder, or splice each left subtree into place as I walk down the right side." That one sentence shows you see the structure rather than memorizing code. Practicing this kind of narration is where many people struggle in a live round: the code is in your head, but explaining it under time pressure is a different skill. Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, surfacing hints and structure while you talk, which can keep you on track when your nerves try to take over.
Created Nov 18, 2026 00:59 Expires Nov 18, 2027 00:59