114. Flatten Binary Tree to Linked List

Linked List Stack Tree Depth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

Pre-order traversal visits root -> left -> right. The flattened list follows the same order using right pointers. The Morris-style in-place approach: for each node with a left child, find the rightmost node of the left subtree, link it to the right child, move the left subtree to right, and null out left.

Algorithm

1curr = root. While curr != null:
2If curr.left != null: find the rightmost node of curr.left (call it rightmost).
3rightmost.right = curr.right. curr.right = curr.left. curr.left = null.
4curr = curr.right.

Example Walkthrough

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

1.curr=1. left=2. Rightmost of 2 = 4. Link 4.right=5. 1.right=2, 1.left=null. List:1->2->3->4->5->6.
2.curr=2. left=3. Rightmost=3. Link 3.right=4. 2.right=3, 2.left=null.
3.Continue until all left pointers are null.

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

Common Pitfalls

•Move the left subtree to right BEFORE advancing curr - otherwise you lose the right child.

114.cs

// Approach: Iterative pre-order traversal using an explicit stack.
// Push the right child first, then the left child, so the left is popped (visited) first.
// For each dequeued node, set node.right to the next item on the stack and node.left to null.
// This rewires all pointers in-place to form a right-only singly linked list in pre-order.
// Time: O(n) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public void Flatten(TreeNode root)
    {
        if (root == null)
            return;

        var st = new Stack<TreeNode>();
        st.Push(root);

        while (st.Count > 0)
        {
            root = st.Pop();

            if (root.right != null)
                st.Push(root.right);

            if (root.left != null)
                st.Push(root.left);

            if (st.Count > 0)
                root.right = st.Peek();
            root.left = null;
        }
    }
}

Was this solution helpful?