Given a binary tree, write a program to flatten it to a linked list. The flattening of the binary tree should be in-place.

Problem Note

  • Note that the left child of all nodes should be NULL.

For example

Input: Given the following binary tree 
    4
   / \
  5   8
 / \   \
6   7   9
Output: The flattened tree should look like:
4
 \
  5
   \
    6
     \
      7
       \
        8
         \
          9