Flatten Binary Tree To Linked List

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        
        flatten(root->left);
        flatten(root->right);
        
        TreeNode* temp = root->right;
        root->right = root->left;
        root->left = nullptr;
        
        while (root->right != nullptr) {
            root = root->right;
        }
        
        root->right = temp;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left != null) {
            TreeNode rightMost = root.left;
            while (rightMost.right != null) {
                rightMost = rightMost.right;
            }
            
            rightMost.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        
        flatten(root.right);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void flatten(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    
    if(root->left){
        flatten(root->left);
        
        struct TreeNode* temp = root->right;
        root->right = root->left;
        root->left = NULL;
        
        struct TreeNode* current = root->right;
        while(current->right){
            current = current->right;
        }
        current->right = temp;
    }
    
    flatten(root->right);
}

                                            
/**
 * Definition for a binary tree node.
 * 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;
        }
        
        Flatten(root.left);
        Flatten(root.right);
        
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        
        while (root.right != null) {
            root = root.right;
        }
        
        root.right = temp;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = this.right = null
 */

var flatten = function(root) {
    if (!root) {
        return;
    }
    
    const stack = [root];
    
    while (stack.length) {
        const node = stack.pop();
        
        if (node.right) {
            stack.push(node.right);
        }
        
        if (node.left) {
            stack.push(node.left);
        }
        
        if (stack.length) {
            node.right = stack[stack.length - 1];
        }
        
        node.left = null;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function flatten(root: TreeNode | null): void {
    if (!root) return;
    
    let queue: TreeNode[] = [];
    preorderTraversal(root, queue);
    
    for (let i = 1; i < queue.length; i++) {
        root.left = null;
        root.right = queue[i];
        root = root.right;
    }
};

function preorderTraversal(node: TreeNode, queue: TreeNode[]): void {
    if (!node) return;
    
    queue.push(node);
    preorderTraversal(node.left, queue);
    preorderTraversal(node.right, queue);
}

                                            
class Solution {

    /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     public $val = null;
     *     public $left = null;
     *     public $right = null;
     *     function __construct($value) {
     *         $this->val = $value;
     *     }
     * }
     */

    /**
     * @param TreeNode $root
     * @return NULL
     */
    function flatten($root) {
        if (!$root) return;
        
        $stack = [];
        $stack[] = $root;
        
        while (!empty($stack)) {
            $node = array_pop($stack);
            
            if ($node->right) {
                $stack[] = $node->right;
            }
            if ($node->left) {
                $stack[] = $node->left;
            }
            
            if (!empty($stack)) {
                $node->right = $stack[count($stack) - 1];
            }
            $node->left = null;
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func flatten(_ root: TreeNode?) {
        var current = root
        while current != nil {
            if let left = current?.left {
                var pre = left
                while pre.right != nil {
                    pre = pre.right!
                }
                pre.right = current?.right
                current?.right = left
                current?.left = nil
            }
            current = current?.right
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
    if root == nil {
        return
    }

    stack := []*TreeNode{root}
    var prev *TreeNode

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if prev != nil {
            prev.Right = node
            prev.Left = nil
        }

        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }

        prev = node
    }
}

                                            
class TreeNode
    attr_accessor :val, :left, :right
    def initialize(val = 0, left = nil, right = nil)
        @val = val
        @left = nil
        @right = nil
    end
end

def flatten(root)
    return if root.nil?
    
    flatten(root.left)
    flatten(root.right)
    
    temp = root.right
    root.right = root.left
    root.left = nil
    
    current = root
    current = current.right while current.right
    current.right = temp
end

To solve this coding challenge, we need to understand the problem requirements and implement a solution that flattens a binary tree into a linked list using pre-order traversal. The right child pointer of each node should point to the next node in the list, and the left child pointer should be null.

# Explanation

The challenge involves manipulating a binary tree structure to transform it into a single, right-skewed list that reflects a pre-order traversal. Pre-order traversal means visiting the root node first, then recursively visiting the left subtree, followed by the right subtree.

Requirements:

Modify the original tree in place (O(1) extra space).
Ensure the resultant list represents a pre-order traversal.

High-Level Approach:

Traverse the tree using a stack to simulate the recursive behavior without using extra space inherent in recursion.
Begin from the root node and process nodes in pre-order fashion.
Maintain a stack to store nodes temporarily.
For each node, visit the node, push its right child onto the stack (if it exists), then push its left child onto the stack (if it exists).
Adjust the pointers such that the left child pointer of the current node is always null, and the right child pointer points to the next node in pre-order traversal.

Step-by-Step Explanation:

Initialization :

Check if the root is null. If null, there is nothing to flatten, so return immediately.

Stack Setup :

Initialize a stack and push the root node onto it. This simulates the beginning of the pre-order traversal.

Iteration and Node Processing :

While the stack is not empty, continue processing:

Pop the node from the stack, which represents the current node.
If the current node has a right child, push it onto the stack. This ensures the right child is processed after the left child but before siblings.
If the current node has a left child, push it onto the stack.
If the stack is not empty, adjust the current node's right pointer to point to the node on the top of the stack, ensuring the correct pre-order linkage.
Set the current node's left child to null.

# Detailed Steps in Pseudocode:

                                            
// Definition of TreeNode:
// class TreeNode {
//   value
//   left child (TreeNode)
//   right child (TreeNode)
// }

// Function to flatten the binary tree to a linked list
function flattenBinaryTreeToLinkedList(rootNode):
    // Base case: if the root node is null, return immediately
    if rootNode is null:
        return

    // Initialize a stack to keep track of nodes to process
    stack = create new stack
    stack.push(rootNode)

    // Process nodes until the stack is empty
    while stack is not empty:
        // Pop the top node from the stack as the current node to process
        currentNode = stack.pop()

        // If the current node has a right child, push it onto the stack
        if currentNode.rightChild is not null:
            stack.push(currentNode.rightChild)

        // If the current node has a left child, push it onto the stack
        if currentNode.leftChild is not null:
            stack.push(currentNode.leftChild)

        // If the stack is not empty, set the current node's right child to the next node in pre-order
        if stack is not empty:
            currentNode.rightChild = stack.top()

        // Set the current node's left child to null, as the left pointers are not used in the linked list format
        currentNode.leftChild = null

// Example use case to call the function:
// rootNode = [ Example Tree ]
// flattenBinaryTreeToLinkedList(rootNode)
// The tree rooted at 'rootNode' should now be flattened into a linked list

By following this detailed explanation and accompanying pseudocode, you will be able to transform a binary tree into a linked list following the pre-order traversal sequence. This method ensures in-place modification of the original tree without requiring additional space, as dictated by the follow-up constraint of the problem.