Flatten Binary Tree to Linked List

Problem

Given the root of a binary tree, flatten the tree into a "linked list":

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

Solution Approach

Expected Time complexity: $O(n)$

Click - to see solution code

C++

class Solution {
    vector<int> preorder;

   public:
    void traversal(TreeNode* root) {
        if (!root) return;
        preorder.push_back(root->val);
        traversal(root->left);
        traversal(root->right);
    }

    void flatten(TreeNode* root) {
        if (root == NULL) return;
        traversal(root);
        root->left = NULL;
        root->right = NULL;
        root->val = preorder[0];
        TreeNode* tmp = root;
        for (int i = 1; i < preorder.size(); i++) {
            TreeNode* newNode = new TreeNode(preorder[i]);
            tmp->right = newNode;
            tmp = newNode;
        }
    }
};