Given a binary tree, connect the nodes that are at the same level. The structure of the tree Node contains an addition nextRight pointer for this purpose.
Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node.
       10                       10 ------> NULL
      / \                       /      \
     3   5       =>     3 ------> 5 --------> NULL
    / \     \               /  \           \
   4   1   2          4 --> 1 -----> 2 -------> NULL
 
Example 1:
Input:
     3
   /  \
  1    2
Output:
3 1 2
1 3 2
Explanation:The connected tree is
       3 ------> NULL
     /   \
    1---> 2 -----> NULL
Example 2:
Input:
      10
    /   \
   20   30
  /  \
 40  60
Output:
10 20 30 40 60
40 20 60 10 30
Explanation:The connected tree is
        10 ---> NULL
       /   \
     20---> 30 ---> NULL
   /   \
 40---> 60 ---> NULL
Your Task:
You don't have to read input or print anything. Complete the function connect() that takes the root of the tree as  input parameter and connects the nodes that lie at the same level. 
Note: The generated output will contain 2 lines. First line contains the level order traversal of the tree and second line contains the inorder traversal of the tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ Number of nodes ≤ 10^{5}
0 ≤ Data of a node ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3





'''

:param root: root of the given tree

:return: none, just connect accordingly.

{

    # Node Class:

    class Node:

        def __init__(self,val):

            self.data = val

            self.left = None

            self.right = None

            self.nextRight = None

}

'''



class Solution:

    def connect(self, root):

        # code here

        



Solutions:
from collections import deque

class Solution:

	def searchNext(self, root, layer, layer_list):
		if root is None:
			return
		else:
			if len(layer_list) == layer:
				tmp_list = [root]
				layer_list.append(tmp_list)
			else:
				layer_list[layer][-1].nextRight = root
				layer_list[layer].append(root)
			self.searchNext(root.left, layer + 1, layer_list)
			self.searchNext(root.right, layer + 1, layer_list)

	def connect(self, root):
		layer_list = []
		self.searchNext(root, 0, layer_list)
		return root


from collections import deque

class Solution:

	def connect(self, root):
		que = deque()
		que.append(root)
		size = 1
		while size > 0:
			size = len(que)
			prev = None
			for i in range(size):
				curr = que.popleft()
				if prev is not None:
					prev.nextRight = curr
				if curr.left is not None:
					que.append(curr.left)
				if curr.right is not None:
					que.append(curr.right)
				prev = curr
				if i == size - 1:
					curr.nextRight = None
		return root


class Solution:

	def searchNext(self, root, layer, layer_list):
		if root is None:
			return
		else:
			if len(layer_list) == layer:
				tmp_list = [root]
				layer_list.append(tmp_list)
			else:
				layer_list[layer][-1].nextRight = root
				layer_list[layer].append(root)
			self.searchNext(root.left, layer + 1, layer_list)
			self.searchNext(root.right, layer + 1, layer_list)

	def connect(self, root):
		layer_list = []
		self.searchNext(root, 0, layer_list)
		return root


class Solution:

	def connect(self, root):
		d = {}
		l = 0

		def preo(root, l):
			if root == None:
				return root
			try:
				d[l].append(root)
			except:
				d.__setitem__(l, [root])
			preo(root.left, l + 1)
			preo(root.right, l + 1)
		l = preo(root, 0)
		for i in d.keys():
			for j in range(1, len(d[i])):
				d[i][j - 1].nextRight = d[i][j]
		return root


class Solution:

	def connect(self, root):
		q = [root]
		while len(q) > 0:
			l = len(q)
			for i in range(l):
				temp = q[0]
				q.pop(0)
				if i == 0:
					cur = temp
				else:
					cur.nextRight = temp
					cur = cur.nextRight
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)


class Solution:

	def connect(self, root):
		if root:
			arr = []
			arr.append(root)
			while len(arr) > 0:
				n = len(arr)
				prev = None
				for x in range(n):
					curr = arr.pop(0)
					if prev is not None:
						prev.nextRight = curr
					prev = curr
					if curr.left:
						arr.append(curr.left)
					if curr.right:
						arr.append(curr.right)
				prev = None
		return


class Solution:

	def connect(self, root):
		s1 = [root]
		s2 = []
		while s1 != []:
			if len(s1) > 1:
				for i in range(len(s1) - 1):
					s1[i].nextRight = s1[i + 1]
			for j in s1:
				if j.left != None:
					s2.append(j.left)
				if j.right != None:
					s2.append(j.right)
			s1 = s2
			s2 = []


class Solution:

	def connect(self, root):
		if not root:
			return
		queue = [root]
		while queue:
			prev = None
			size = len(queue)
			for _ in range(size):
				curr = queue.pop(0)
				if prev:
					prev.nextRight = curr
				prev = curr
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)


from collections import deque

class Solution:

	def connect(self, root):
		queue = deque()
		queue.append((root, 0))
		while queue:
			(node, level) = queue.popleft()
			if node.left:
				queue.append((node.left, level + 1))
			if node.right:
				queue.append((node.right, level + 1))
			if queue:
				if level == queue[0][1]:
					node.nextRight = queue[0][0]
		return root


class Solution:

	def connect(self, root):
		q = [root]
		while q:
			lis = []
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if lis:
					lis[-1].nextRight = node
				lis.append(node)
		return root


class Solution:

	def connect(self, root):
		queue = [root, None]
		i = 0
		while i < len(queue):
			if queue[i] == None and i == len(queue) - 1:
				break
			if queue[i] == None:
				queue.append(None)
				i += 1
				continue
			if queue[i].left:
				queue.append(queue[i].left)
			if queue[i].right:
				queue.append(queue[i].right)
			i += 1
		i = 0
		while i < len(queue):
			if queue[i]:
				queue[i].nextRight = queue[i + 1]
			i += 1


class Solution:

	def connect(self, root):
		stack = [root]
		new_stack = []
		while stack:
			n = len(stack)
			for i in range(n):
				node = stack.pop(0)
				if stack:
					node.nextRight = stack[0]
				else:
					node.nextRight = None
				if node.left:
					new_stack.append(node.left)
				if node.right:
					new_stack.append(node.right)
			stack = new_stack[:]
			new_stack = []


from collections import deque

class Solution:

	def connect(self, root):
		q = deque()
		prev_node = None
		prev_level = 0
		q.append((root, prev_level))
		while q:
			(node, level) = q.popleft()
			next_level = level + 1
			if node.left:
				q.append((node.left, next_level))
			if node.right:
				q.append((node.right, next_level))
			if prev_node and prev_level == level:
				prev_node.nextRight = node
			prev_node = node
			prev_level = level


class Solution:

	def connect(self, root):
		q = [root]
		while len(q) > 0:
			l = len(q)
			inlen = l
			while l > 0:
				temp = q[0]
				if l == inlen:
					prev = temp
				else:
					prev.nextRight = temp
					prev = temp
				q.pop(0)
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
				l -= 1
		return


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while len(q):
			curr_level_size = len(q)
			for i in range(curr_level_size):
				curr_node = q[0]
				if i != curr_level_size - 1:
					curr_node.nextRight = q[1]
				if curr_node.left:
					q.append(curr_node.left)
				if curr_node.right:
					q.append(curr_node.right)
				q.pop(0)


class Solution:

	def connect(self, root):
		stack = [root]
		helper = []
		while stack:
			depth = len(stack)
			for _ in range(depth):
				top = stack.pop(0)
				if top.left:
					stack.append(top.left)
					helper.append(top.left)
				if top.right:
					stack.append(top.right)
					helper.append(top.right)
			n = len(helper) - 1
			for i in range(n):
				(l, r) = (helper[i], helper[i + 1])
				l.nextRight = r
			helper.clear()


class Solution:

	def connect(self, root):
		self.helper(root, [])

	def helper(self, node, right_nodes, level=1):
		if node is None:
			return
		if len(right_nodes) < level:
			right_nodes.append(node)
		else:
			node.nextRight = right_nodes[level - 1]
			right_nodes[level - 1] = node
		self.helper(node.right, right_nodes, level + 1)
		self.helper(node.left, right_nodes, level + 1)


class Solution:

	def connect(self, root):
		dq = deque([root])
		levels = []
		while dq:
			level = []
			for _ in range(len(dq)):
				cur = dq.popleft()
				level.append(cur)
				if cur.left:
					dq.append(cur.left)
				if cur.right:
					dq.append(cur.right)
			levels.append(level)
		for level in levels:
			for (a, b) in zip(level, level[1:]):
				a.nextRight = b


class Solution:

	def connect(self, root):
		queue = [root]
		while queue:
			for i in range(len(queue) - 1):
				queue[i].nextRight = queue[i + 1]
			queue[-1].nextRight = None
			temp_queue = []
			for i in range(len(queue)):
				if queue[i].left:
					temp_queue.append(queue[i].left)
				if queue[i].right:
					temp_queue.append(queue[i].right)
			queue = temp_queue
		return root


class Solution:

	def connect(self, root):
		q = deque()
		q.append(root)
		root.nextRight = None
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			for i in range(len(q)):
				if i == len(q) - 1:
					q[i].nextRight = None
				else:
					q[i].nextRight = q[i + 1]


from collections import deque

class Solution:

	def connect(self, root):
		dq = deque()
		dq.append(root)
		while len(dq) > 0:
			currsize = len(dq)
			for i in range(currsize):
				temp = dq.popleft()
				if i == currsize - 1:
					temp.nextRight = None
				else:
					temp.nextRight = dq[0]
				if temp.left != None:
					dq.append(temp.left)
				if temp.right != None:
					dq.append(temp.right)
		return root


class Solution:

	def connect(self, root):
		Q = []
		Q.append(root)
		temp = root
		while len(Q) > 0:
			n = len(Q)
			if n == 1:
				node = Q.pop(0)
				node.nextRight = None
				if node.left:
					Q.append(node.left)
				if node.right:
					Q.append(node.right)
			else:
				for i in range(n - 1):
					node = Q.pop(0)
					node.nextRight = Q[0]
					if node.left:
						Q.append(node.left)
					if node.right:
						Q.append(node.right)
				node = Q.pop(0)
				node.nextRight = None
				if node.left:
					Q.append(node.left)
				if node.right:
					Q.append(node.right)


class Solution:

	def connect(self, root):
		if not root:
			return None
		q = [root]
		while len(q) != 0:
			prev = q[0]
			if len(q) == 1:
				q[0].nextRight = None
			for i in q[1:]:
				prev.nextRight = i
				prev = i
			q[-1].nextRight = None
			x = len(q)
			for i in range(x):
				temp = q.pop(0)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)


class Solution:

	def connect(self, root):
		q = deque()
		q.append(root)
		while q:
			temp = None
			for i in range(len(q)):
				p = q.pop()
				p.nextRight = temp
				temp = p
				if p.right:
					q.appendleft(p.right)
				if p.left:
					q.appendleft(p.left)
		return root


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while q:
			prev = None
			x = len(q)
			for i in range(x):
				k = q.pop(0)
				if i != 0:
					prev.nextRight = k
				prev = k
				if k.left != None:
					q.append(k.left)
				if k.right != None:
					q.append(k.right)
			prev.nextRight = None


from collections import defaultdict

class Solution:

	def connect(self, root):
		levels = defaultdict(lambda : Node)

		def dfs(root, level):
			if not root:
				return
			dfs(root.left, level + 1)
			dfs(root.right, level + 1)
			if levels[level] == None:
				levels[level] = root
			else:
				levels[level].nextRight = root
				levels[level] = root
		dfs(root, 0)


class Solution:

	def connect(self, root):
		q = deque()
		q.append(root)
		root.nextRight = None
		while q:
			l1 = []
			i = len(q)
			while i > 0:
				n = q.popleft()
				l1.append(n)
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
				i -= 1
			for j in range(len(l1) - 1):
				l1[j].nextRight = l1[j + 1]
		return root


class Solution:

	def connect(self, root):

		def levelorder(root):
			queue = [[root]]
			while queue:
				z = queue.pop(0)
				p = []
				p = p + z
				li = []
				for i in range(len(p)):
					h = p[i]
					if h.left is not None:
						li.append(h.left)
					if h.right is not None:
						li.append(h.right)
				if li != []:
					queue.append(li)
				for i in range(len(z)):
					if i == len(z) - 1:
						continue
					else:
						z[i].nextRight = z[i + 1]
		h = levelorder(root)
		return root


from collections import deque

class Solution:

	def connect(self, root):
		q = deque()
		q.append(root)
		while q:
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if i == n - 1:
					node.nextRight = None
				else:
					node.nextRight = q[0]
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)


from collections import deque

class Solution:

	def getchild(self, root):
		return [root.left, root.right]

	def connect(self, root):
		qu = deque()
		qu.append(root)
		while qu:
			prev = None
			for _ in range(len(qu)):
				node = qu.popleft()
				if prev:
					prev.nextRight = node
				prev = node
				for x in self.getchild(node):
					if x:
						qu.append(x)


import collections

class Solution:

	def connect(self, root):
		if not root:
			return None
		queue = collections.deque()
		queue.append(root)
		while queue:
			count = len(queue)
			for i in range(0, count):
				curr = queue.popleft()
				if i == count - 1:
					curr.nextRight = None
				else:
					curr.nextRight = queue[0]
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
		return root


class Solution:

	def connect(self, root):
		level = list()
		level.append(root)
		while len(level) > 0:
			nextlevel = list()
			prevnode = None
			for node in level:
				if node.left is not None:
					nextlevel.append(node.left)
				if node.right is not None:
					nextlevel.append(node.right)
				if prevnode is not None:
					prevnode.nextRight = node
				prevnode = node
			level = nextlevel


class Solution:

	def connect(self, root):
		hash = {}

		def fun(root, level):
			if root == None:
				return
			if level in hash:
				hash[level][-1].nextRight = root
				hash[level].append(root)
			else:
				hash[level] = [root]
			fun(root.left, level + 1)
			fun(root.right, level + 1)
		fun(root, 0)


from collections import deque

class Solution:

	def connect(self, root):
		queue = deque([root])
		while queue:
			innerQueue = queue
			queue = deque()
			for _ in range(len(innerQueue)):
				curr = innerQueue.popleft()
				if len(innerQueue) > 0:
					curr.nextRight = innerQueue[0]
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)


import collections

class Solution:

	def connect(self, root):
		q = collections.deque()
		q.append(root)
		while q:
			qLen = len(q)
			prev = None
			first = 1
			for i in range(qLen):
				cur = q.popleft()
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
				if first:
					prev = cur
					first = 0
				elif not first:
					prev.nextRight = cur
					prev = cur


from collections import deque

class Solution:

	def connect(self, root):
		d = deque()
		d.append(root)
		while d:
			l = len(d)
			level = []
			for i in range(l):
				node = d[i]
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
				if i > 0:
					d[i - 1].nextRight = d[i]
			d = deque(level)
		return root


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while q:
			n = len(q)
			while n:
				tmp = q.pop(0)
				if tmp.left:
					q.append(tmp.left)
				if tmp.right:
					q.append(tmp.right)
				n -= 1
			for i in range(len(q) - 1):
				q[i].nextRight = q[i + 1]
			if len(q):
				q[len(q) - 1].nextRight = None
		return root


class Solution:

	def connect(self, root):
		if root is None:
			return
		que = [root]
		while que:
			prev = None
			for i in range(len(que)):
				node = que.pop(0)
				if prev != None:
					prev.nextRight = node
				prev = node
				if node.left != None:
					que.append(node.left)
				if node.right != None:
					que.append(node.right)


class Solution:

	def connect(self, root):
		q = []
		lst = []
		q.append([root, 0])
		while len(q) > 0:
			temp = q.pop(0)
			lst.append(temp)
			node = temp[0]
			level = temp[1]
			if node.left != None:
				q.append([node.left, level + 1])
			if node.right != None:
				q.append([node.right, level + 1])
		for i in range(len(lst) - 1):
			if lst[i][1] == lst[i + 1][1]:
				lst[i][0].nextRight = lst[i + 1][0]
			else:
				lst[i][0].nextRight = None


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while len(q):
			queue = []
			for data in q:
				if data.left is not None:
					queue.append(data.left)
				if data.right is not None:
					queue.append(data.right)
			i = 0
			while i < len(q) - 1:
				q[i].nextRight = q[i + 1]
				i += 1
			q[i].nextRight = None
			q = queue


class Solution:

	def connect(self, root):
		level = -1
		before = root
		q = []
		q.append([root, 0])
		while q:
			c = q.pop(0)
			if c[1] == level:
				before.nextRight = c[0]
			else:
				level += 1
			before = c[0]
			if c[0].left != None:
				q.append([c[0].left, level + 1])
			if c[0].right != None:
				q.append([c[0].right, level + 1])


class Solution:

	def connect(self, root):
		store = []
		self.helper(root, 0, store)
		for item in store:
			for i in range(len(item) - 1):
				item[i].nextRight = item[i + 1]
		return

	def helper(self, root, level, store):
		if root is None:
			return
		if len(store) == level:
			store.append([])
		store[level].append(root)
		self.helper(root.left, level + 1, store)
		self.helper(root.right, level + 1, store)
		return


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while q:
			l = len(q)
			for i in range(l):
				temp = q[0]
				if i != l - 1:
					temp.nextRight = q[1]
				q.pop(0)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)


class Solution:

	def connect(self, root):

		def level(r, d, l):
			if not r:
				return
			level(r.left, d, l + 1)
			if l in d:
				d[l].append(r)
			else:
				d[l] = [r]
			level(r.right, d, l + 1)
		d = {}
		level(root, d, 0)
		for (k, v) in d.items():
			for i in range(1, len(v)):
				v[i - 1].nextRight = v[i]


from collections import defaultdict

class Solution:

	def connect(self, root):
		depth = defaultdict(lambda : None)

		def bfs():
			q = deque([(root, 0)])
			while q:
				(node, d) = q.popleft()
				if not node:
					continue
				if not depth[d]:
					depth[d] = node
				else:
					depth[d].nextRight = node
					depth[d] = node
				q.extend([(node.left, d + 1), (node.right, d + 1)])
		bfs()
		return root


class Solution:

	def connect(self, root):
		if not root:
			return
		queue = [root]
		while queue:
			level_size = len(queue)
			for i in range(level_size):
				node = queue.pop(0)
				if i < level_size - 1:
					node.nextRight = queue[0]
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)


class Solution:
	dp = dict()

	def solve(self, root, level):
		if root == None:
			return
		self.solve(root.left, level + 1)
		if level in self.dp.keys():
			self.dp[level].nextRight = root
		self.dp[level] = root
		self.solve(root.right, level + 1)

	def connect(self, root):
		self.dp = dict()
		self.solve(root, 0)


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while q:
			a = q
			q = []
			prev = None
			for x in reversed(a):
				x.nextRight = prev
				prev = x
			for x in a:
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while q:
			a = q[:]
			q.clear()
			prev = None
			for i in reversed(range(len(a))):
				a[i].nextRight = prev
				prev = a[i]
			for x in a:
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)


class Solution:

	def connect(self, root):
		q = [root]
		while q:
			node = None
			for i in range(len(q)):
				curr = q.pop(0)
				if curr.right:
					q.append(curr.right)
				if curr.left:
					q.append(curr.left)
				curr.nextRight = node
				node = curr


class Solution:

	def connect(self, root):
		q = [root]
		while q:
			temp = []
			for _ in range(len(q)):
				node = q.pop(0)
				if q:
					node.nextRight = q[0]
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			q += temp
		return root


class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		while q:
			size = len(q)
			while size > 0:
				temp = q.pop(0)
				size -= 1
				if size == 0:
					temp.nextRight = None
				else:
					temp.nextRight = q[0]
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)


class Solution:

	def connect(self, root):
		list1 = [root, None]
		ans = []
		l = 2
		while l >= 2:
			if list1[0] == None:
				list1.pop(0)
				list1.append(None)
			list1[0].nextRight = list1[1]
			if list1[0].left != None:
				list1.append(list1[0].left)
				l += 1
			if list1[0].right != None:
				list1.append(list1[0].right)
				l += 1
			ans.append(list1.pop(0))
			l -= 1
		ans2 = []


import queue as q

class Solution:

	def connect(self, root):
		q1 = []
		q1.append(root)
		while q1:
			prevtemp = None
			for i in range(len(q1)):
				temp = q1.pop(0)
				if temp.left:
					q1.append(temp.left)
				if temp.right:
					q1.append(temp.right)
				if prevtemp:
					prevtemp.nextRight = temp
				prevtemp = temp


class Solution:

	def connect(self, root):
		a = []
		a.append(root)
		while len(a) > 0:
			n = len(a)
			prv = None
			for i in range(n):
				curr = a[0]
				a = a[1:]
				if prv != None:
					prv.nextRight = curr
				prv = curr
				if curr.left != None:
					a.append(curr.left)
				if curr.right != None:
					a.append(curr.right)
			prv = None


class Solution:

	def connect(self, root):
		q = [root]
		while q:
			p = q[0]
			n = len(q)
			for i in range(n):
				if not q[0]:
					q.pop(0)
					continue
				if i != 0:
					p.nextRight = q[0]
					p = p.nextRight
				if q[0].left:
					q.append(q[0].left)
				if q[0].right:
					q.append(q[0].right)
				q.pop(0)
			p.next = None


class Solution:
	REM = None

	def connect(self, root):
		d = {}
		height = self.get_h(root)
		for i in range(height):
			Solution.REM = None
			a = self.set_connection(root, i)

	def get_h(self, root):
		if root != None:
			l = self.get_h(root.left)
			r = self.get_h(root.right)
			return max(l, r) + 1
		else:
			return 0

	def set_connection(self, root, k):
		assigned = False
		if root == None:
			return
		elif k == 0:
			return root
		else:
			left = self.set_connection(root.left, k - 1)
			right = self.set_connection(root.right, k - 1)
			if left:
				if Solution.REM:
					Solution.REM.nextRight = left
				assigned = True
				Solution.REM = left
			if right:
				if not assigned and Solution.REM:
					Solution.REM.nextRight = right
				Solution.REM = right
			if left and right:
				left.nextRight = right
			return


class Solution:

	def connect(self, root):
		queue = []
		queue.append(root)
		queue.append(None)
		while queue:
			p = queue.pop(0)
			if p:
				p.nextRight = queue[0]
				if p.left:
					queue.append(p.left)
				if p.right:
					queue.append(p.right)
			elif queue:
				queue.append(None)


from collections import defaultdict

class Solution:

	def connect(self, root):
		dic = defaultdict(list)

		def trans(node, i):
			if not node:
				return
			dic[i].append(node)
			trans(node.left, i + 1)
			trans(node.right, i + 1)
		trans(root, 0)
		for i in dic.values():
			for j in range(len(i)):
				if j == len(i) - 1:
					i[j].nextRight = None
				else:
					i[j].nextRight = i[j + 1]
		return root


class Solution:

	def connect(self, root):
		if root.left == None and root.right == None:
			return root
		queue = [root]
		while queue:
			l = len(queue)
			for i in range(l):
				x = queue.pop(0)
				if i == l - 1:
					x.nextRight = None
				else:
					x.nextRight = queue[0]
				if x.left:
					queue.append(x.left)
				if x.right:
					queue.append(x.right)


class Solution:

	def connect(self, root):

		def helper(root):
			q = []
			t = []
			if not root:
				return
			q.append(root)
			prev = None
			while q:
				for i in range(len(q)):
					a = q.pop(0)
					if prev == None:
						prev = a
					else:
						prev.nextRight = a
						prev = a
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
				prev = None
		helper(root)


from collections import defaultdict

class Solution:

	def helper(self, root, level, mp):
		if not root:
			return
		mp[level].append(root)
		self.helper(root.left, level + 1, mp)
		self.helper(root.right, level + 1, mp)

	def connect(self, root):
		mp = defaultdict(list)
		self.helper(root, 1, mp)
		for k in mp:
			for i in range(len(mp[k]) - 1):
				mp[k][i].nextRight = mp[k][i + 1]
			mp[k][len(mp[k]) - 1].nextRight = None
		return root