This problem requires flattening a binary tree into a right-skewed linked list in-place by carefully adjusting each node's left and right pointers. The solution can be recursive or iterative using a stack, ensuring the original tree structure is traversed in pre-order. Managing pointer reassignment without losing subtree references is crucial to avoid breaking the sequence and producing incorrect outputs.
Problem Statement
Given the root of a binary tree, flatten the tree into a 'linked list' following the pre-order traversal sequence. Each node's left child must be null, and the right child points to the next node in this traversal. The flattened structure should maintain the relative order of nodes exactly as encountered during pre-order processing, ensuring all original subtree nodes are linked properly without creating cycles or skipping nodes.
You must implement this transformation in-place without creating new tree nodes. The tree may be empty or contain up to 2000 nodes, each with values ranging from -100 to 100. Pay attention to edge cases such as single-node trees, fully left-skewed or right-skewed trees, and null nodes. Correct handling of left subtree reassignment and right-pointer propagation is essential to preserve the pre-order sequence. Examples include root = [1,2,5,3,4,null,6] flattening to [1,null,2,null,3,null,4,null,5,null,6].
Examples
Example 1
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Example details omitted.
Example 2
Input: root = []
Output: []
Example details omitted.
Example 3
Input: root = [0]
Output: [0]
Example details omitted.
Constraints
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
Solution Approach
Recursive Pre-order Re-linking
Use a recursive approach where you traverse the tree in pre-order and flatten each subtree before connecting it. At each node, recursively flatten the left and right subtrees, then reassign the left subtree as the node's right child, and append the original right subtree at the end of the new right chain. This approach requires careful handling of null pointers to avoid breaking the linked-list sequence. Recursive backtracking ensures each node is processed only once while maintaining the pre-order pattern.
Iterative Stack-Based Flattening
Implement an iterative solution using a stack to simulate pre-order traversal. Push nodes onto the stack starting with the root, then process nodes by popping from the stack, setting the current node's right child to the next node from pre-order, and nullifying the left child. Push the right child first, then the left child to ensure correct order. This prevents losing subtrees and avoids recursion depth limits, but careful pointer management is required to maintain the flattened sequence without accidentally skipping nodes.
Morris Traversal Modification
Use a Morris traversal-like method to flatten the tree in-place without extra space. For each node with a left child, find the rightmost node of the left subtree and link its right pointer to the current node's right child. Then move the left subtree to the right and set the left pointer to null. Continue iterating to the right child. This method reduces space complexity compared to recursion or stack approaches but requires precise pointer reassignment to preserve the pre-order sequence and avoid overwriting important links.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because each node is visited once during pre-order traversal. Space complexity can be O(h) for recursion stack or O(n) for an explicit stack, or O(1) using the Morris traversal method. The provided complexities depend on the approach chosen, but all ensure linear processing relative to the number of nodes in the tree.
What Interviewers Usually Probe
- Do you see how flattening in pre-order affects the linked list pointer reassignment?
- Can you implement this in-place without using extra nodes or arrays?
- Will you correctly handle edge cases such as null or single-node trees while preserving order?
Common Pitfalls or Variants
Common pitfalls
- Forgetting to nullify the left child after moving the left subtree to the right can break the flattened structure.
- Incorrectly appending the original right subtree may lead to nodes being skipped or duplicated.
- Using a stack incorrectly may reverse the order of nodes, violating pre-order traversal sequence.
Follow-up variants
- Flatten to a doubly-linked list preserving pre-order sequence with both next and previous pointers.
- Flatten the tree in post-order instead of pre-order, testing pointer reassignment logic differently.
- Flatten a n-ary tree to a linked list while maintaining pre-order traversal for multiple children per node.
How GhostInterview Helps
- Capture or screenshot tree input to track traversal steps and subtree manipulations visually.
- Provide guided answer path showing recursive, iterative, and Morris traversal approaches with explicit time and space complexity.
- Support screen-share workflows capturing pointer reassignments and tree layers to verify correct pre-order flattening step by step.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Flatten Binary Tree to Linked List?
The primary pattern is linked-list pointer manipulation along a pre-order traversal, converting left subtrees to the right pointers while nullifying left children.
Can I solve this problem iteratively?
Yes, an iterative solution uses a stack to simulate pre-order traversal, pushing right then left children to maintain the correct sequence while reassigning pointers.
How do I handle null nodes in this flattening problem?
Null nodes should be skipped during traversal; ensure left children are nullified and right pointers link only valid nodes to maintain the linked list structure.
Is there a space-optimized approach?
Yes, using a Morris traversal-like technique allows in-place flattening with O(1) extra space by rewiring pointers without recursion or stack usage.
What are common mistakes when flattening the tree?
Common errors include not nullifying left children, misplacing the original right subtree, and reversing nodes due to incorrect stack push order, all of which break pre-order flattening.
Need direct help with Flatten Binary Tree to Linked List instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Flatten Binary Tree to Linked List from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Connect each node across every level by reusing established next links to traverse a perfect binary tree without extra queue storage.
Open problem page#117 Populating Next Right Pointers in Each Node IIPopulate each next pointer in a binary tree to its immediate right node, handling nulls and uneven levels efficiently using pointer manipulation.
Open problem page#94 Binary Tree Inorder TraversalBinary Tree Inorder Traversal asks you to visit left subtree, node, then right subtree without losing position while moving through the tree.
Open problem page