Flatten Binary Tree to Linked List

You are given the root of a binary tree. Your task is to transform this binary tree into a "linked list" structure in-place. The structure should follow the pre-order traversal of the original tree, where each node's right child points to the next node in the traversal, and its left child is always null.

Problem Description

The goal is to flatten a binary tree into a linked list. This means restructuring the tree such that:

• Every node's left child pointer is set to null.
• Every node's right child pointer points to the next node in the pre-order traversal of the original tree.

The flattening must be done in-place, meaning you should modify the existing tree nodes without creating new ones.

Key Requirements:

• The resulting structure should resemble a linked list, where node.right points to the next element and node.left is null.
• The order of nodes in the flattened list must correspond to the pre-order traversal (Root, Left, Right).

Edge Cases:

• An empty tree (root is null).
• A tree with only a root node.
• A tree that is already a left-skewed or right-skewed structure.

Examples

Example 1:

Input:

    1
   / \
  2   5
 / \   \
3   4   6

Output:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Explanation: The pre-order traversal is 1, 2, 3, 4, 5, 6. The tree is rearranged so that each node's right child points to the next node in this sequence, and all left children become null.

Example 2:

Input:

      0

Output:

      0

Explanation: A single node tree remains unchanged as its pre-order traversal is just the node itself.

Example 3:

Input:

null

Output:

null

Explanation: An empty tree results in an empty flattened list.

Constraints

• The number of nodes in the tree will be between 0 and 2000.
• Node values will be integers.
• You should aim for an efficient solution, ideally with a time complexity of O(N) where N is the number of nodes, and a space complexity of O(1) if using an iterative approach, or O(H) if using a recursive approach (where H is the height of the tree).

Notes

Consider how you might perform a pre-order traversal and simultaneously modify the pointers. Think about the state you need to maintain as you move from one node to the next in the flattened list. For recursive solutions, the return value of a recursive call might be important. For iterative solutions, a stack or careful pointer manipulation will be key.