binary tree flattening algorithm this code defines an algorithm to flatten a binary tree into a linked list represented using the right pointers of the tree nodes it uses inplace flattening and demonstrates the flattening process along with a display function to visualize the flattened linked list https www geeksforgeeks orgflattenabinarytreeintolinkedlist arunkumar a date 04092023 a treenode has data variable and pointers to treenode objects for its left and right children build and return a sample binary tree returns treenode the root of the binary tree examples root buildtree root data 1 root left data 2 root right data 5 root left left data 3 root left right data 4 root right right data 6 flatten a binary tree into a linked list inplace where the linked list is represented using the right pointers of the tree nodes args root treenode the root of the binary tree to be flattened examples root treenode1 root left treenode2 root right treenode5 root left left treenode3 root left right treenode4 root right right treenode6 flattenroot root data 1 root right right is none false root right right treenode3 root right right right is none true flatten the left subtree save the right subtree make the left subtree the new right subtree find the end of the new right subtree append the original right subtree to the end flatten the updated right subtree display the flattened linked list args root treenode none the root of the flattened linked list examples root treenode1 root right treenode2 root right right treenode3 displaylinkedlistroot 1 2 3 root none displaylinkedlistroot a treenode has data variable and pointers to treenode objects for its left and right children build and return a sample binary tree returns treenode the root of the binary tree examples root build_tree root data 1 root left data 2 root right data 5 root left left data 3 root left right data 4 root right right data 6 flatten a binary tree into a linked list in place where the linked list is represented using the right pointers of the tree nodes args root treenode the root of the binary tree to be flattened examples root treenode 1 root left treenode 2 root right treenode 5 root left left treenode 3 root left right treenode 4 root right right treenode 6 flatten root root data 1 root right right is none false root right right treenode 3 root right right right is none true flatten the left subtree save the right subtree make the left subtree the new right subtree find the end of the new right subtree append the original right subtree to the end flatten the updated right subtree display the flattened linked list args root treenode none the root of the flattened linked list examples root treenode 1 root right treenode 2 root right right treenode 3 display_linked_list root 1 2 3 root none display_linked_list root
from __future__ import annotations


class TreeNode:
    

    def __init__(self, data: int) -> None:
        self.data = data
        self.left: TreeNode | None = None
        self.right: TreeNode | None = None


def build_tree() -> TreeNode:
    
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(5)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.right = TreeNode(6)
    return root


def flatten(root: TreeNode | None) -> None:
    
    if not root:
        return

    
    flatten(root.left)

    
    right_subtree = root.right

    
    root.right = root.left
    root.left = None

    
    current = root
    while current.right:
        current = current.right

    
    current.right = right_subtree

    
    flatten(right_subtree)


def display_linked_list(root: TreeNode | None) -> None:
    
    current = root
    while current:
        if current.right is None:
            print(current.data, end="")
            break
        print(current.data, end=" ")
        current = current.right


if __name__ == "__main__":
    print("Flattened Linked List:")
    root = build_tree()
    flatten(root)
    display_linked_list(root)