Flatten Binary Tree to Linked List

Problem Statement

The given problem requires us to transform a binary tree into a flattened "linked list" using the same TreeNode class structure. In this flattened structure, every node's left child pointer will be null, and the right child pointer will point to the next node in the sequence that mimics the order of a pre-order traversal of the binary tree. Pre-order traversal is a depth-first strategy where we visit the root node first, followed by the left subtree, and finally the right subtree. This transformation must effectively turn the binary tree into a linear sequence of nodes, consistent with the pre-order visitation order.

Examples

Example 1

Input:

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

Output:

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

Example 2

Input:

root = []

Output:

[]

Example 3

Input:

root = [0]

Output:

[0]

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Approach and Intuition

The challenge is straightforward yet requires a careful manipulation of tree nodes to achieve the desired linked list format. Here is a step-by-step explanation of a potential approach:

1. Start at the root of the binary tree. If the tree is empty (i.e., the root is null), there is nothing to flatten, so we simply return.

2. As we need to flatten the tree to resemble a pre-order traversal, we will follow the root-left-right order in our approach.

3. Initiate the transformation at the root and traverse the tree. Use an iterative or recursive method to process each node:

   • For each node, if it has a left child, find the rightmost node of the left subtree. This rightmost node will be connected to the current node's right subtree.
   • Make the current node's left subtree its right subtree and set the left child to null.
   • Continue to the next node on the right and repeat the process until all nodes are processed.

4. This can be either implemented recursively, where the recursive function ensures after processing a node, it directly connects to the next node in pre-order, or iteratively using a stack to mimic the recursive stack and manage the order of nodes manually.

5. Care should be taken at each node to:

   • Preserve the order.
   • Properly connect the rightmost node of the left subtree to the right subtree before making changes.
   • Ensure no left children remain by setting them explicitly to null.

• With these steps carefully implemented, the binary tree will be flattened into a singly linked list in the image of its pre-order traversal, adhering to the problem's constraints on tree size and node values.

Solutions

class Solution {
public:
    void flattenTree(TreeNode* current) {
        if (!current)
            return;
            
        TreeNode* temp = current;
        while (temp != nullptr) {
            if (temp->left != nullptr) {
                TreeNode* rightTail = temp->left;
                while (rightTail->right != nullptr) {
                    rightTail = rightTail->right;
                }
                rightTail->right = temp->right;
                temp->right = temp->left;
                temp->left = nullptr;
            }
            temp = temp->right;
        }
    }
};