Flatten Binary Tree to Linked List - CPP Solution

1. Introduction

In this blog post, we explore a problem that involves transforming a binary tree into a linked list. This problem is a unique blend of tree manipulation and linked list construction, where the tree is flattened in such a way that it follows the same order as a pre-order traversal.

Problem

Given the root of a binary tree, the task is to flatten the tree into a "linked list". The "linked list" should use the same TreeNode class where the right child points to the next node in the list and the left child is always null. The order should be the same as a pre-order traversal of the binary tree.

2. Solution Steps

1. Perform a pre-order traversal of the binary tree.

2. While traversing, rearrange the nodes so that each node's right child points to the next node in the pre-order sequence and the left child is set to null.

3. Continue this process until all nodes are rearranged into the linked list.

3. Code Program

#include <iostream>
using namespace std;

// TreeNode structure definition
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Function to flatten the binary tree into a linked list
void flatten(TreeNode* root) {
    TreeNode* curr = root;
    while (curr) {
        if (curr->left) {
            TreeNode* prev = curr->left;
            while (prev->right) {
                prev = prev->right; // Find the rightmost node
            }
            prev->right = curr->right; // Connect the right subtree
            curr->right = curr->left;  // Move the left subtree
            curr->left = nullptr;      // Set the left child to null
        }
        curr = curr->right; // Move to the next node in pre-order
    }
}

// Function to print the flattened tree (linked list)
void printFlattenedTree(TreeNode* root) {
    while (root) {
        cout << root->val << " -> ";
        root = root->right;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(6);

    flatten(root);
    printFlattenedTree(root); // Expected output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> nullptr
    return 0;
}

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> nullptr

Explanation:

The flatten function transforms the binary tree into a linked list using the pre-order traversal pattern. 

For each node, if it has a left child, the function finds the rightmost node in the left subtree and connects it to the right subtree. 

Then, it moves the entire left subtree to the right and sets the left child to null. 

This process rearranges the tree nodes in the same order as a pre-order traversal and effectively flattens the tree into a linked list. 

The printFlattenedTree function is used to demonstrate the structure of the flattened tree.