Given the root of a binary tree, flatten the tree into a "linked list":
	The "linked list" should use the same Node class where the right child pointer points to the next   node in the list and the left child pointer is always null.
	The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Example 1:
Input : 
          1
        /   \
       2     5
      / \     \
     3   4     6
Output :
1 2 3 4 5 6 
Explanation: 
After flattening, the tree looks 
like this
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6 
Here, left of each node points 
to NULL and right contains the 
next node in preorder.The inorder 
traversal of this flattened tree 
is 1 2 3 4 5 6.
Example 2:
Input :
        1
       / \
      3   4
         /
        2
         \
          5 
Output : 
1 3 4 2 5  
Explanation : 
After flattening, the tree looks 
like this 
     1
      \
       3
        \
         4
          \
           2
            \ 
             5 
Here, left of each node points 
to NULL and right contains the 
next node in preorder.The inorder 
traversal of this flattened tree 
is 1 3 4 2 5.
Your task:
You don't have to read input or print anything. Your task is to complete the function flatten() which takes the root of the tree and flattens the tree into a linkes list without using any auxiliary space.
Note : The driver code prints the inorder traversal of the flattened binary tree.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
 
Constraints :
1<=n<=10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def flatten(self, root):

        #code here

Solutions:
class Solution:

	def flatten(self, root):
		stack = [(root, False)]
		dummy = Node(-1)
		curr = dummy
		while stack:
			(node, visited) = stack.pop()
			if visited:
				curr.right = node
				node.left = None
				curr = node
			elif node:
				stack.append((node.right, False))
				stack.append((node.left, False))
				stack.append((node, True))
		return dummy


class Solution:

	def inorder(self, root):
		if root:
			self.inorder(root.left)
			print(root.data, end=' ')
			self.inorder(root.right)

	def flatten(self, root):
		stack = [(root, False)]
		ans = []
		dummy = Node(-1)
		curr = dummy
		while stack:
			(node, visited) = stack.pop()
			if visited:
				curr.right = node
				node.left = None
				curr = node
			elif node:
				stack.append((node.right, False))
				stack.append((node.left, False))
				stack.append((node, True))
		return dummy


class Solution:

	def flatten(self, root):
		curr = root
		while curr:
			if curr.left != None:
				prev = curr.left
				while prev.right:
					prev = prev.right
				prev.right = curr.right
				curr.right = curr.left
				curr.left = None
			curr = curr.right


class Solution:

	def flatten(self, root):
		if root is None:
			return None
		stack = []
		dummy = Node(0)
		curr = dummy
		stack.append(root)
		while len(stack) != 0:
			node = stack.pop()
			if node.right is not None:
				stack.append(node.right)
			if node.left is not None:
				stack.append(node.left)
			curr.right = node
			node.left = None
			curr = node
		return dummy.right


class Solution:

	def flatten(self, root):
		if not root:
			return None
		prev = None

		def r(rt):
			nonlocal prev
			if rt is None:
				return None
			r(rt.right)
			r(rt.left)
			rt.right = prev
			rt.left = None
			prev = rt
		r(root)
		return root


class Solution:

	def util(self, root):
		if root == None:
			return root
		if root.left == None and root.right == None:
			return root
		l = self.util(root.left)
		r = self.util(root.right)
		if l != None:
			root.left = None
			root.right = l
			if r != None:
				temp = l
				while temp.right != None:
					temp = temp.right
				temp.right = r
			return root
		else:
			root.left = None
			if r != None:
				root.right = r
			return root

	def flatten(self, root):
		return self.util(root)


class Solution:
	prev = None

	def flatten(self, root):
		if root == None:
			return
		self.flatten(root.right)
		self.flatten(root.left)
		root.right = self.prev
		root.left = None
		self.prev = root


class Solution:

	def flatten(self, root):
		curr = root
		while curr is not None:
			if curr.left is not None:
				pred = curr.left
				while pred.right is not None:
					pred = pred.right
				pred.right = curr.right
				curr.right = curr.left
				curr.left = None
			curr = curr.right


class Solution:

	def flatten(self, root):
		prev = None

		def fun(root):
			if root is None:
				return
			fun(root.right)
			fun(root.left)
			nonlocal prev
			root.right = prev
			root.left = None
			prev = root
		fun(root)
		return prev


class Solution:

	def flatten(self, root):
		prev_node = None

		def sol(root):
			nonlocal prev_node
			if not root:
				return
			sol(root.right)
			sol(root.left)
			root.right = prev_node
			root.left = None
			prev_node = root
		sol(root)


class Solution:

	def flatten(self, root):
		self.temp = None
		self.solve(root)

	def solve(self, root):
		if root.right is not None:
			self.solve(root.right)
		if root.left is not None:
			self.solve(root.left)
		root.left = None
		root.right = self.temp
		self.temp = root


class Solution:

	def flatten(self, root):

		def helper(curr, prev=None):
			if not curr:
				return prev
			if prev:
				prev.right = curr
			temp = curr.right
			curr.right = curr.left
			curr.left = None
			helper(curr.right)
			use_prev = root
			while use_prev.right:
				use_prev = use_prev.right
			helper(temp, use_prev)
		helper(root)
		return root


class Solution:

	def flatten(self, root):
		arr = []

		def pre(root):
			if not root:
				return
			arr.append(root)
			pre(root.left)
			pre(root.right)
		pre(root)
		head = root = arr[0]
		arr.pop(0)
		root.left = None
		while len(arr) > 0:
			root.right = arr.pop(0)
			root.left = None
			root = root.right


class Solution:

	def flatten(self, root):
		if root is None:
			return None
		if not root.left and (not root.right):
			return root
		left = self.flatten(root.left)
		right = self.flatten(root.right)
		if left and (not right):
			root.right = root.left
			root.left = None
			return root
		if not left and right:
			return root
		temp = root.right
		root.right = left
		l = root.left
		while l.right:
			l = l.right
		l.right = temp
		root.left = None
		return root