Flatten Binary Tree to Linked List
Right-root-left reverse traversal — append each node to the front of a growing chain.
2 min read
tree dfs
Problem#
Flatten a binary tree into a “linked list” in place, where each node’s left is null and right points to the next preorder node.
Examples#
[1,2,5,3,4,null,6]→[1,null,2,null,3,null,4,null,5,null,6][]→[]
Constraints#
- The number of nodes is in
[0, 2000].
Approach#
Reverse-preorder traversal (right, left, root) with a prev pointer. At each node, set its right to prev, its left to null, and update prev to itself.
Solution#
class Solution {public: void flatten(TreeNode* root) { TreeNode* prev = nullptr; function<void(TreeNode*)> dfs = [&](TreeNode* u) { if (!u) return; dfs(u->right); dfs(u->left); u->right = prev; u->left = nullptr; prev = u; }; dfs(root); }};func flatten(root *TreeNode) { var prev *TreeNode var dfs func(*TreeNode) dfs = func(u *TreeNode) { if u == nil { return } dfs(u.Right) dfs(u.Left) u.Right = prev u.Left = nil prev = u } dfs(root)}from typing import Optional
class Solution: def flatten(self, root: Optional[TreeNode]) -> None: self.prev: Optional[TreeNode] = None
def dfs(u: Optional[TreeNode]) -> None: if u is None: return dfs(u.right) dfs(u.left) u.right = self.prev u.left = None self.prev = u
dfs(root)var flatten = function(root) { let prev = null; const dfs = (u) => { if (u === null) return; dfs(u.right); dfs(u.left); u.right = prev; u.left = null; prev = u; }; dfs(root);};class Solution { private TreeNode prev = null;
public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right = prev; root.left = null; prev = root; }}function flatten(root: TreeNode | null): void { let prev: TreeNode | null = null; const dfs = (u: TreeNode | null): void => { if (u === null) return; dfs(u.right); dfs(u.left); u.right = prev; u.left = null; prev = u; }; dfs(root);}Editorial#
Walking right-left-root visits nodes in reverse preorder. Since we always prepend the current node to the already-built suffix, the chain naturally ends up in preorder. Stashing prev avoids needing a return value.
Complexity#
- Time: O(n).
- Space: O(h).
Concept revision#
Related#