Given a Binary Tree, write a function to populate next pointer for all nodes. The next pointer for every node should be set to point to inorder successor.
Example 1:
Input:
           10
       /  \
      8    12
     /
    3
  
Output: 3->8 8->10 10->12 12->-1
Explanation: The inorder of the above tree is :
3 8 10 12. So the next pointer of node 3 is 
pointing to 8 , next pointer of 8 is pointing
to 10 and so on.And next pointer of 12 is
pointing to -1 as there is no inorder successor 
of 12.
Example 2:
Input:
           1
      /   \
     2     3
Output: 2->1 1->3 3->-1 
Your Task:
You do not need to read input or print anything. Your task is to complete the function populateNext() that takes the root node of the binary tree as input parameter.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=n<=10^5
1<=data of the node<=10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

        self.next=None



class Solution:

    def populateNext(self,root):

        pass



Solutions:
class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.next = None

class Solution:

	def inorder(self, root, prev):
		if root is None:
			return
		self.inorder(root.left, prev)
		prev[0].next = root
		prev[0] = root
		self.inorder(root.right, prev)

	def populateNext(self, root):
		dummy = Node(-1)
		prev = [dummy]
		self.inorder(root, prev)
		return dummy.next


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.next = None
succ = None

class Solution:

	def populateNext(self, root):
		global succ
		succ = None

		def popNext(root):
			global succ
			if root:
				popNext(root.right)
				root.next = succ
				succ = root
				popNext(root.left)
		popNext(root)


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.next = None

class Solution:

	def populateNext(self, root):
		if root is None:
			return
		if root.left is None and root.right is None:
			return [root, root]
		d = [root, root]
		if root.left is not None:
			l = self.populateNext(root.left)
			l[1].next = root
			d[0] = l[0]
		if root.right is not None:
			r = self.populateNext(root.right)
			root.next = r[0]
			d[1] = r[1]
		return d


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.next = None

class Solution:

	def inorder(self, root):
		if root is None:
			return
		self.inorder(root.left)
		if self.arr != []:
			self.arr[0].next = root
			self.arr.pop()
		self.arr.append(root)
		self.inorder(root.right)

	def populateNext(self, root):
		pass
		self.arr = []
		self.inorder(root)


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.next = None

class Solution:

	def populateNext(self, root):

		def inord(root, a):
			if root is None:
				return
			inord(root.left, a)
			if a != []:
				a[0].next = root
				a.pop()
			a.append(root)
			inord(root.right, a)
		a = []
		inord(root, a)


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.next = None

class Solution:

	def inorder(self, root):
		if root:
			self.inorder(root.left)
			self.ans.append(root)
			self.inorder(root.right)

	def populateNext(self, root):
		self.ans = []
		self.inorder(root)
		for i in range(len(self.ans) - 1):
			self.ans[i].next = self.ans[i + 1]
		self.ans[-1] = Node(-1)
		return


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.next = None

class Solution:

	def populateNext(self, root):

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			self.li.append(root)
			inorder(root.right)

		def traverse():
			i = 0
			while i < len(self.li) - 1:
				self.li[i].next = self.li[i + 1]
				i += 1
		self.li = []
		inorder(root)
		traverse()
		return self.li[0]


class Solution:

	def populateNext(self, root):

		def solve(node, prev):
			if not node:
				return
			solve(node.left, prev)
			if prev[0]:
				prev[0].next = node
			prev[0] = node
			solve(node.right, prev)
		prev = [None]
		solve(root, prev)