Leet Code Problem #114. 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

Approach to the solution:

1. Traverse the left sub tree until the left most leaf found recursively.
2. Store the right child in temp variable.
   
3. Take that left node and make it as right child of leaf parent.
4. Now traverse through the right child of the parent until the leaf node is found.
5. Assign its right child as temp.
6. Do the same thing for right sub tree as well.
   

Solution in C++: 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        cal(root);
    }
    
    void cal(TreeNode* root){        
        if(!root)
            return;        
        if(root->right){
            cal(root->right);
        }
        if(root->left){
            cal(root->left);
        }
        if(root->left){
            TreeNode* temp = root->right;
            root->right = root->left;
            root->left = nullptr;
            while(root->right)
                root = root->right;
            root->right = temp;
        }
    }
};