Flatten Binary Tree to Linked List
Medium · Graphs · Explanation and code example
Iterative Pointer Rewiring
How it works
Preorder visits the left subtree before the right subtree. Attach the original right subtree to the rightmost node of the left subtree, then move the left subtree to the right link. Continue along the right chain, gradually forming the required preorder list.
Steps
- If a left child exists, find its rightmost node.
- Attach the old right subtree there and move the left subtree to root.right.
- Clear root.left and advance to root.right.
Complexity
- Time: O(n); predecessor scans and the main walk traverse edges a bounded number of times.
- Space: O(1).
Things to watch for
- Save the original right subtree through rewiring so it is not lost.
- Every left pointer must become null.
- The tree is modified in place; no new list nodes are needed.
Python code example
class Solution:
def flatten(self, root: TreeNode | None) -> None:
if not root:
return
while root:
if root.left:
# Find the rightmost root
rightmost = root.left
while rightmost.right:
rightmost = rightmost.right
# Rewire the connections
rightmost.right = root.right
root.right = root.left
root.left = None
# Move on to the right side of the tree
root = root.right
C++ code example
class Solution {
public:
void flatten(TreeNode* root) {
if (root == nullptr)
return;
while (root != nullptr) {
if (root->left != nullptr) {
// Find the rightmost root.
TreeNode* rightmost = root->left;
while (rightmost->right != nullptr)
rightmost = rightmost->right;
// Rewire the connections.
rightmost->right = root->right;
root->right = root->left;
root->left = nullptr;
}
// Move on to the right side of the tree.
root = root->right;
}
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.