Flatten Binary Tree to Linked List

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;
        }
    }
};

The given C++ code defines a method flattenTree within a Solution class to convert a binary tree into a flattened linked list. The transformation adheres to these rules: it places each node to the right of its previous node, effectively turning the tree into a right-skewed linked list in the same order as a pre-order traversal.

Here's a simplified breakdown of how the code works:

• The function accepts a pointer to the root node of a binary tree.
• If the input node is null, the function returns immediately, handling the base case where the tree might be empty.
• The function utilizes a loop to process each node of the tree starting from the given root. Inside the loop:
  • If a node has a left child, it locates the rightmost node of the left subtree.
  • Once found, it attaches the right subtree of the current node to this rightmost node's right pointer.
  • It then adjusts the current node's right pointer to point to its left child (effectively moving the left subtree to the right).
  • The left pointer of the current node is set to null.
  • This process repeats for the next right node.

This method does not return any value as it modifies the tree in place. The algorithm implicitly handles the tree flattening without needing any additional memory for storage, which makes it space-efficient with a time complexity that, generally speaking, is O(n), where n is the number of nodes in the tree. This is because it processes each node in the tree exactly once.

class Solution {
    public void flattenTree(TreeNode root) {
        if (root == null) return; // Check if the root is null

        TreeNode currentNode = root;

        while (currentNode != null) {
            if (currentNode.left != null) {
                TreeNode farRight = currentNode.left;
                while (farRight.right != null) {
                    farRight = farRight.right;
                }

                farRight.right = currentNode.right;
                currentNode.right = currentNode.left;
                currentNode.left = null;
            }

            currentNode = currentNode.right;
        }
    }
}

Flatten a binary tree into a linked list using Java with the provided code. This tutorial ensures the binary tree's in-order elements are transformed into a linked list along the right child pointers.

Begin with checking if the root node is null. Traverse the tree using a while loop, initiating with the root node. Inside the loop, consider the left child of the current node. If the left child exists:

1. Identify the rightmost node of the left subtree to connect it to the right subtree.
2. Move through the left subtree until reaching the farthest right node, then link this node's right pointer to the current right subtree.
3. Reassign the current node's right subtree to be its left subtree, setting the left child to null to flatten the structure effectively.

Proceed through the right subtree and repeat until all nodes are adjusted.

This restructuring allows the original binary tree to take the form of a linked list flattened along the rightmost elements, ensuring the tree's depth is minimized to one node thick, with all children branching off to the right. This simplistic and iterative approach efficiently traverses and modifies the tree in place, leveraging existing tree links without requiring additional data structures.

struct TreeNode* tree_flatten(struct TreeNode* root) {
    if (!root) return NULL;
    struct TreeNode* currentNode = root;
    while (currentNode != NULL) {
        if (currentNode->left != NULL) {
            struct TreeNode* leftSubtree = currentNode->left;
            while (leftSubtree->right != NULL) {
                leftSubtree = leftSubtree->right;
            }
            leftSubtree->right = currentNode->right;
            currentNode->right = currentNode->left;
            currentNode->left = NULL;
        }
        currentNode = currentNode->right;
    }
    return root;
}

The solution provided transforms a binary tree into a linked list by modifying its structure in place. This transformation ensures each node only retains its right child, effectively creating a singly linked list consisting of the original tree's pre-order traversal.

• Begin by confirming if the root is NULL. If so, immediately return NULL to handle the base case of an empty tree.
• Initialize currentNode with root to start the processing from the tree's root.
• Use a while loop to navigate through the tree until currentNode becomes NULL.
• Inside the loop, check if the currentNode has a left child:
  • If it does, locate the rightmost node of the left subtree. This becomes a connecting point.
  • Update the rightmost node’s right pointer to the currentNode's right child.
  • Adjust the currentNode's right pointer to point to the left child, effectively moving the left subtree to the right.
  • Set the currentNode's left pointer to NULL to sever the original left linkage.
• Move through the list by advancing currentNode to its right child.
• Return the modified root after exiting the loop, which now serves as the head of the flattened list.

This implementation not only flattens the binary tree but also ensures that all operations are performed in place without the need for additional memory allocation, leveraging the original tree's nodes.

var flattenTree = function (tree) {
    if (!tree) {
        return;
    }
    let currentNode = tree;
    while (currentNode !== null) {
        if (currentNode.left !== null) {
            let lastRight = currentNode.left;
            while (lastRight.right !== null) {
                lastRight = lastRight.right;
            }
            lastRight.right = currentNode.right;
            currentNode.right = currentNode.left;
            currentNode.left = null;
        }
        currentNode = currentNode.right;
    }
};

The problem, "Flatten Binary Tree to Linked List," involves transforming a given binary tree into a "linked list" in a specific manner, which adheres to the tree's preorder traversal.

Here's how the JavaScript solution, flattenTree, works to solve this problem:

1. Check if the input tree is null, in which case, end the function as there are no operations needed on an empty tree.
2. Initialize currentNode as a pointer to the root of the tree to traverse and manipulate the tree structure.
3. Use a while loop to iterate through the nodes of the tree until there are no more nodes (currentNode is null).
4. Within each iteration, check if the current node (currentNode) has a left child.
5. If a left child exists, find the rightmost child of this left subtree, referred to as lastRight.
6. Modify the tree's structure:
   • Link the rightmost node of the left subtree (lastRight.right) to the right child of the current node (currentNode.right).
   • Make the left child of the current node become the right child (currentNode.right = currentNode.left).
   • Ensure the original left link of currentNode is eliminated (currentNode.left = null) to adhere to the linked list structure.
7. Move to the next node in the sequence by setting currentNode to currentNode.right, which now contains the subsequent elements in preorder due to the adjustments made.

Ensure the entire tree is processed, resulting in the left pointers of all nodes being null, and the right pointers creating a linked list reflecting the preorder traversal order of the original binary tree.

class Solution:

    def flatten_tree(self, root: TreeNode) -> None:
        if not root:
            return None

        current = root
        while current:
            if current.left:
                last_right = current.left
                while last_right.right:
                    last_right = last_right.right
                
                last_right.right = current.right
                current.right = current.left
                current.left = None
            
            current = current.right

The provided Python code transforms a binary tree into a flattened linked list. When executed, the tree is modified in-place to resemble a singly linked list, which primarily utilizes the right child pointers.

• Begin with the root node and progress through the nodes, iteratively adjusting pointers.
• If a node has a left child, locate the rightmost child of this left subtree.
• Redirect the original right subtree of the current node to become the right child of this rightmost node.
• The left subtree is then moved to the right, effectively flattening that portion of the tree.
• Nullify the left pointer to adhere to the singly linked list structure.
• Move to the right, progressing linearly down the linked list structure that's being created.

By continuously shifting subtrees and adjusting pointers accordingly, this algorithm flattens the binary tree directly without the need for additional data structures, ensuring efficient space utilization.