Algorithm-Day47-Flatten-Binary-Tree-to-Linked-List-lc-114

Posted on In , Views:

🧩 Problem Description

Given the root of a binary tree, flatten it to a linked list in-place.
The linked list should follow the same order as a pre-order traversal.

💬 Example

1
2
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

💡 Approach 1: Reverse Preorder DFS

We can do a reverse preorder traversal (right → left → root) and keep track of the previous node to build the flattened list.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}

💡 Approach 2: Iterative with Stack

We can also simulate preorder traversal using a stack and rearrange pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();

            if (curr.right != null) stack.push(curr.right);
            if (curr.left != null) stack.push(curr.left);

            if (!stack.isEmpty()) {
                curr.right = stack.peek();
            }
            curr.left = null;
        }
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — visiting all nodes once.
  • Space Complexity: O(h) for recursion / stack (O(n) in worst case).

✍️ Summary

  • Reverse preorder DFS is a neat trick because it avoids extra temporary storage.
  • Iterative stack solution is more explicit and easier to debug.
  • Related problems:
    • lc-116 — Populating Next Right Pointers in Each Node
    • lc-430 — Flatten a Multilevel Doubly Linked List