text: # Time:  O(n)
  # Space: O(h), h is height of binary tree
  #
  # 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
  #
  
  # Definition for a  binary tree node
  class TreeNode:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
  
  class Solution:
      # @param root, a tree node
      # @return nothing, do it in place
      def flatten(self, root):
          return self.flattenRecu(root, None)
          
      def flattenRecu(self, root, list_head):
          if root != None:
              list_head = self.flattenRecu(root.right, list_head)
              list_head = self.flattenRecu(root.left, list_head)
              root.right = list_head
              root.left = None
              return root
          else:
              return list_head
          
  class Solution2:
      list_head = None
      # @param root, a tree node
      # @return nothing, do it in place
      def flatten(self, root):
          if root != None:
              self.flatten(root.right)
              self.flatten(root.left)
              root.right = self.list_head
              root.left = None
              self.list_head = root
              return root
          
  if __name__ == "__main__":
      root = TreeNode(1)
      root.left = TreeNode(2)
      root.left.left = TreeNode(3)
      root.left.right = TreeNode(4)
      root.right = TreeNode(5)
      root.right.right = TreeNode(6)
      result = Solution().flatten(root)
      print result.val
      print result.right.val
      print result.right.right.val
      print result.right.right.right.val
      print result.right.right.right.right.val
      print result.right.right.right.right.right.val
  