Flatten Binary Tree to Linked List - Java Solution

1. Introduction

In this blog post, we tackle a unique tree manipulation problem - flattening a binary tree into a linked list. This task involves reorganizing the tree so that each node's right child points to the next node in a preorder traversal sequence, effectively creating a singly linked list out of the tree nodes.

Problem

Given the root of a binary tree, the goal is to flatten the tree into a "linked list" using the TreeNode class. In this linked list, each node's right child points to the next node in the list (as per preorder traversal), and the left child pointer is always null.

2. Solution Steps

1. Traverse the tree using a preorder traversal approach.

2. For each node, save its right child and connect its left child to the right.

3. Go to the rightmost node of the new right subtree and connect the saved right child.

4. Continue this process for each node in the tree.

5. Ensure the left child of each node is set to null.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class FlattenBinaryTreeToLinkedList {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        flatten(root);
        // Output can be verified by traversing the right pointers and printing the node values
    }

    // Function to flatten the binary tree into a linked list
    public static void flatten(TreeNode root) {
        TreeNode current = root;
        while (current != null) {
            if (current.left != null) {
                TreeNode rightmost = current.left;
                // Find the rightmost node in the left subtree
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                // Connect the rightmost node to the right subtree
                rightmost.right = current.right;
                // Move the left subtree to the right
                current.right = current.left;
                current.left = null; // Set left child to null
            }
            // Move to the next node in the preorder sequence
            current = current.right;
        }
    }
}

Output:

The binary tree is flattened into a linked list in place. The nodes are rearranged following the preorder traversal order.

Explanation:

1. flatten: This function iterates through each node of the binary tree, applying a specific transformation to flatten the tree into a linked list.

2. At each node, if the left child exists, the function finds the rightmost node of the left subtree.

3. It then attaches the original right subtree to this rightmost node and moves the entire left subtree to the right, effectively removing the left child.

4. The left child of each node is set to null, following the requirements of the linked list.

5. The function continues this process iteratively, moving along the right child pointers, which now represent the next pointers in the linked list.

6. This process transforms the tree in place, aligning with the preorder traversal order.