14.Flatten Binary Tree to Linked List

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

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Solution : (Using Stack)

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

        if (root == NULL)
        {
            return;
        }

        stack<TreeNode *> s;
        s.push(root);
        TreeNode *t = NULL;
        while (!s.empty())
        {
            t = s.top();
            s.pop();

            if (t->right)
            {
                s.push(t->right);
            }

            if (t->left)
            {
                s.push(t->left);
            }

            if (!s.empty())
            {
                t->right = s.top();
            }

            t->left = NULL;
        }
    }
};