Flatten Binary Tree to Linked List

Problem Statement

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution


class Solution {
public:
    void flatten(TreeNode *root) {

       TreeNode* prev = NULL;
       flattenHelper(root,prev);

    }
    void flattenHelper(TreeNode* root,TreeNode*& prev) //Needed a pre-order traversal
    {
        if( root == NULL )
            return;

        if(prev == NULL)
            prev = root;
        else
        {
            prev->right = root;
            prev->left = NULL;
            prev = prev->right;
        }

        TreeNode* right = root->right;

        flattenHelper(root->left,prev);

        flattenHelper(right,prev);
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s