Flatten Binary Tree to Linked List

This challenge asks you to transform a given binary tree into a sorted linked list. The linked list should represent an in-order traversal of the binary tree, with each node of the tree becoming a node in the linked list. This problem is useful for understanding tree traversal algorithms and manipulating tree structures.

Problem Description

You are given the root of a binary tree. Your task is to flatten the binary tree into a sorted linked list using an in-order traversal. The linked list should be formed by connecting the nodes of the tree sequentially in the order they are visited during the in-order traversal. The left and right children of each node in the original binary tree should be discarded; only the 'value' of each node should be preserved in the linked list.

What needs to be achieved:

• Convert the binary tree into a sorted linked list.
• The linked list should be sorted in ascending order based on the node values (in-order traversal).
• The original tree structure should be modified in-place.

Key Requirements:

• The linked list should be a singly linked list.
• The linked list should be sorted in ascending order.
• The original binary tree should be modified in-place; no new tree nodes should be created.

Expected Behavior:

Given a binary tree, the function should return the head of the sorted linked list. If the input tree is empty (root is null), the function should return null.

Edge Cases to Consider:

• Empty tree (root is null).
• Tree with only one node.
• Skewed trees (left-skewed or right-skewed).
• Trees with duplicate values.

Examples

Example 1:

Input:
    1
   / \
  2   5
     / \
    3   4

Output:

1 -> 2 -> 3 -> 4 -> 5

Explanation: The in-order traversal of the tree is 1, 2, 3, 4, 5. These values are then linked together to form the sorted linked list.

Example 2:

Input:
    5
   / \
  3   6
 / \
2   4

Output:

2 -> 3 -> 4 -> 5 -> 6

Explanation: The in-order traversal of the tree is 2, 3, 4, 5, 6. These values are linked to form the sorted linked list.

Example 3: (Edge Case - Single Node)

Input:
    1

Output:

1

Explanation: The tree consists of a single node with value 1. The linked list will also contain only one node with value 1.

Constraints

• The number of nodes in the binary tree can range from 0 to 100,000.
• The values of the nodes are integers.
• The values of the nodes are unique (no duplicates).
• The solution should have a time complexity of O(N), where N is the number of nodes in the tree.
• The solution should have a space complexity of O(H), where H is the height of the tree (due to recursion stack). Iterative solutions are encouraged to minimize space complexity.

Notes

• Consider using recursion or an iterative approach (e.g., using a stack) to perform the in-order traversal.
• You will need to create a linked list node structure (if your language doesn't provide one).
• Remember to handle the edge case of an empty tree.
• The in-order traversal ensures that the linked list will be sorted in ascending order.
• Focus on modifying the tree in-place to create the linked list. Avoid creating new nodes for the linked list if possible.