Given a binary tree, connect the nodes that are at same level. You'll be given an addition nextRight pointer for the same.
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 take input. Complete the function connect() that takes root as parameter and connects the nodes at same level. The printing is done by the driver code. First line of the output will be level order traversal and second line will be inorder travsersal
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ Number of nodes ≤ 105
0 ≤ Data of a node ≤ 105

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3



import sys

sys.setrecursionlimit(50000)

# Tree Node

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

        self.nextRight = None

class Solution:

    #Function to connect nodes at same level.

    def connect(self, root):

        





Solutions:
import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
from collections import deque
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		cur_level = deque()
		next_level = deque()
		cur_level.append(root)
		while cur_level:
			cur_node = cur_level.popleft()
			if cur_node.left:
				next_level.append(cur_node.left)
			if cur_node.right:
				next_level.append(cur_node.right)
			if cur_level:
				cur_node.nextRight = cur_level[0]
			else:
				while next_level:
					cur_level.append(next_level.popleft())


import sys
sys.setrecursionlimit(50000)

class Node:

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

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Queue:

	def __init__(self):
		self.lst = []

	def size(self):
		return len(self.lst)

	def isEmpty(self):
		return self.lst == []

	def enqueue(self, data):
		self.lst.append(data)

	def dequeue(self):
		return self.lst.pop(0)

	def getElement(self, idx):
		return self.lst[idx]

class Solution:

	def connect(self, root):
		q = Queue()
		q.enqueue(root)
		treeLevel = dict()
		while not q.isEmpty():
			for i in range(q.size()):
				node = q.dequeue()
				if node.left is not None:
					q.enqueue(node.left)
				if node.right is not None:
					q.enqueue(node.right)
			for i in range(1, q.size()):
				q.getElement(i - 1).nextRight = q.getElement(i)


import sys
sys.setrecursionlimit(50000)

class Node:

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

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:
					pnt = temp
				else:
					pnt.nextRight = temp
					pnt = pnt.nextRight
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
from collections import deque
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		queue = deque()
		queue.append(root)
		while queue:
			n = len(queue)
			prev = None
			for i in range(n):
				node = queue.popleft()
				if prev != None:
					prev.nextRight = node
				prev = node
				if node.left is not None:
					queue.append(node.left)
				if node.right is not None:
					queue.append(node.right)
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = deque()
		q.append(root)
		q.append(None)
		while q:
			node = q.popleft()
			if node is None:
				if q:
					q.append(None)
				continue
			node.nextRight = q[0]
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = []
		q.append([root, 0])
		while len(q) != 0:
			curr = q[0][0]
			lev = q[0][1]
			q.pop(0)
			if lev == 0 or len(q) == 0:
				curr.nextRight = None
			if len(q) != 0 and q[0][1] == lev:
				curr.nextRight = q[0][0]
			if curr.left != None:
				q.append([curr.left, lev + 1])
			if curr.right != None:
				q.append([curr.right, lev + 1])


from collections import deque
import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = deque()
		q.append(root)
		q.append('$')
		prev = None
		while q:
			n = q.popleft()
			if n == '$':
				prev.nextRight = None
				if not q:
					break
				prev = None
				q.append('$')
			else:
				if prev:
					prev.nextRight = n
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
				prev = n
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		dic = {}
		q = deque(list())
		q.append([root, 0])
		size = 1
		while size > 0:
			temp = q[0][0]
			l = q[0][1]
			q.popleft()
			size -= 1
			if temp != None:
				if l in dic.keys():
					dic[l].nextRight = temp
				dic[l] = temp
				q.append([temp.left, l + 1])
				q.append([temp.right, l + 1])
				size += 2


from collections import deque

class Solution:

	def connect(self, node):
		dQ = deque()
		dQ.append(node)
		while dQ:
			times = len(dQ)
			linking = Node(None)
			for i in range(times):
				rootnode = dQ.popleft()
				linking.nextRight = rootnode
				linking = linking.nextRight
				if rootnode.left != None:
					dQ.append(rootnode.left)
				if rootnode.right != None:
					dQ.append(rootnode.right)
			linking.nextRight = None
		return node


from collections import deque
import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = deque([root, None])
		while len(q) != 1:
			ele = q.popleft()
			if ele:
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
				ele.nextRight = q[0]
			else:
				q.append(None)


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


from collections import deque
import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = deque([root])
		while q:
			prev = None
			n = len(q)
			for i in range(0, n):
				cur = q.popleft()
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
				if prev != None:
					prev.nextRight = cur
				prev = cur
			prev.next = None


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = []
		ans = []
		q.append(root)
		while q:
			n = len(q)
			a = []
			for j in range(n):
				node = q.pop(0)
				a.append(node)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			ans.append(a)
		for i in ans:
			for j in range(len(i)):
				if j + 1 < len(i):
					i[j].nextRight = i[j + 1]
				else:
					i[j].nextRight = None


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.nextRight = None
from collections import deque

class Solution:

	def connect(self, root):
		if root is None:
			return root
		x = deque()
		x.append(root)
		prev = None
		while x:
			n = len(x)
			for i in range(n):
				node = x.popleft()
				if i == 0:
					prev = node
				else:
					prev.nextRight = node
				prev = node
				if node.left:
					x.append(node.left)
				if node.right:
					x.append(node.right)
			prev.nextRight = None
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		lst = []
		if root == None:
			return
		queue = deque()
		queue.append(root)
		while queue:
			n = len(queue)
			m = n
			while n:
				if n == m:
					lastNode = queue[-1]
					lastNode.nextRight = None
				node = queue.popleft()
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
				n = n - 1
				if n == 0:
					for i in range(0, len(queue) - 1):
						queue[i].nextRight = queue[i + 1]
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if root is None:
			return
		queue = [(root, 0)]
		while queue:
			(curr, level) = queue.pop(0)
			if len(queue) and queue[0][1] == level:
				curr.nextRight = queue[0][0]
			if curr.left:
				queue.append((curr.left, level + 1))
			if curr.right:
				queue.append((curr.right, level + 1))
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if root is None:
			return None
		head = root
		while head:
			dummy = Node(0)
			currentNode = dummy
			while head:
				if head.left:
					currentNode.nextRight = head.left
					currentNode = currentNode.nextRight
				if head.right:
					currentNode.nextRight = head.right
					currentNode = currentNode.nextRight
				head = head.nextRight
			head = dummy.nextRight
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:
	level_dict = {}

	def connect(self, root):
		self.level_dict = {}
		root = self.traverse(root, 0)
		return root

	def traverse(self, root, level):
		if root == None:
			return root
		if level not in self.level_dict:
			root.nextRight = None
			self.level_dict[level] = root
		else:
			root.nextRight = self.level_dict[level]
			self.level_dict[level] = root
		root.right = self.traverse(root.right, level + 1)
		root.left = self.traverse(root.left, level + 1)
		return root


import sys
import collections
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if not root:
			return
		q = collections.deque()
		q.append((root, 0))
		while len(q):
			(curr_node, curr_ht) = q.popleft()
			if len(q):
				if curr_ht == q[0][1]:
					curr_node.nextRight = q[0][0]
				else:
					curr_node.nextRight = None
			else:
				curr_node.nextRight = None
			if curr_node.left:
				q.append((curr_node.left, curr_ht + 1))
			if curr_node.right:
				q.append((curr_node.right, curr_ht + 1))
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):

		def preorder(root, lvl):
			if root is None:
				lvl -= 1
				return
			if lvl not in d.keys():
				d[lvl] = root
			else:
				n = d[lvl]
				n.nextRight = root
				d[lvl] = root
			preorder(root.left, lvl + 1)
			preorder(root.right, lvl + 1)
		d = {}
		lvl = 0
		preorder(root, lvl)


import sys
sys.setrecursionlimit(50000)

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.nextRight = None
		self.h = 0

class Solution:

	def connect(self, root):
		hashmap = {}
		q = [root]
		root.h = 0
		while q:
			temp = q.pop(0)
			height = temp.h
			if height not in hashmap:
				hashmap[height] = [temp]
			else:
				hashmap[height].append(temp)
			if temp.left is not None:
				temp.left.h = height + 1
				q.append(temp.left)
			if temp.right is not None:
				temp.right.h = height + 1
				q.append(temp.right)
		for i in hashmap:
			l = len(hashmap[i])
			temp = hashmap[i][0]
			for j in range(1, l):
				temp.nextRight = hashmap[i][j]
				temp = hashmap[i][j]
			temp.nextRight = None
		return


from collections import deque
import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if not root:
			return
		if root.left:
			root.left.nextRight = root.right
		if root.nextRight:
			if root.right:
				if root.nextRight.left:
					root.right.nextRight = root.nextRight.left
				elif root.nextRight.right:
					root.right.nextRight = root.nextRight.right
			elif root.left:
				if root.nextRight.left:
					root.left.nextRight = root.nextRight.left
				elif root.nextRight.right:
					root.left.nextRight = root.nextRight.right
		self.connect(root.left)
		self.connect(root.right)
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):

		def findRight(root):
			if not root:
				return None
			temp = root
			while temp:
				if temp.left:
					return temp.left
				if temp.right:
					return temp.right
				temp = temp.nextRight
			return None
		q = [root]
		while q:
			n = len(q)
			while n > 0:
				n -= 1
				node = q.pop(0)
				if node.left:
					q.append(node.left)
					if node.right:
						node.left.nextRight = node.right
					else:
						node.left.nextRight = findRight(node.nextRight)
				if node.right:
					q.append(node.right)
					node.right.nextRight = findRight(node.nextRight)
		return


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		nodes = 1
		curr = None
		newLevel = False
		while q:
			root = q.pop(0)
			nodes -= 1
			if curr:
				curr.nextRight = root
				curr = curr.nextRight
			if newLevel:
				curr = root
				newLevel = False
			if root.left:
				q.append(root.left)
			if root.right:
				q.append(root.right)
			if nodes == 0:
				curr = None
				nodes = len(q)
				newLevel = True


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if root == None:
			return None
		que = [root, None]
		temp = None
		while que:
			r = que.pop(0)
			if r == None:
				if que:
					que.append(None)
					temp = None
			else:
				if r.left:
					que.append(r.left)
				if r.right:
					que.append(r.right)
				if temp == None:
					temp = r
				else:
					temp.nextRight = r
					temp = r
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		temp = [root, '\n']
		i = 0
		while i < len(temp) - 1:
			if i == len(temp) - 1:
				break
			if temp[i] == '\n':
				temp.append('\n')
			else:
				if temp[i].left:
					temp.append(temp[i].left)
				if temp[i].right:
					temp.append(temp[i].right)
			i += 1
		i = 0
		while i < len(temp):
			if temp[i + 1] != '\n':
				temp[i].nextRight = temp[i + 1]
			elif temp[i + 1] == '\n':
				temp[i].next = None
				i += 1
			i += 1


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if not root:
			return None
		queue = [root, None]
		prev = None
		while queue:
			curr = queue.pop(0)
			if curr:
				if prev:
					prev.nextRight = curr
				prev = curr
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			else:
				if queue:
					queue.append(None)
				prev = None
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):

		def walk(node, level, m):
			if not node:
				return
			node.nextRight = m.get(level, None)
			m[level] = node
			walk(node.right, level + 1, m)
			walk(node.left, level + 1, m)
		walk(root, 0, {})
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if not root:
			return None
		q = [root]
		while len(q) != 0:
			prev = q[0]
			for i in q[1:]:
				prev.nextRight = i
				prev = i
			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)
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.nextRight = None
from collections import deque

class Solution:

	def connect(self, root):
		q = deque([root])
		while q:
			sz = len(q)
			nxt = None
			for _ in range(sz):
				n = q.popleft()
				n.nextRight = nxt
				nxt = n
				if n.right:
					q.append(n.right)
				if n.left:
					q.append(n.left)
		return root


class Solution:

	def connect(self, root):
		q = []
		ans = []
		q.append(root)
		while q:
			n = len(q)
			a = []
			for j in range(n):
				node = q.pop(0)
				a.append(node)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			ans.append(a)
		for i in ans:
			for j in range(len(i)):
				if j + 1 < len(i):
					i[j].nextRight = i[j + 1]
				else:
					i[j].nextRight = None


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import collections
import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		queue = collections.deque()
		queue.append(root)
		root.nextRight = None
		while queue:
			size = len(queue)
			prev = Node(None)
			for i in range(size):
				temp = queue.popleft()
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
				if prev != None:
					prev.nextRight = temp
					prev = temp


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):

		def p(t):
			if t == None:
				return None
			l = [t, None]
			z = []
			while len(l) > 1:
				r = l.pop(0)
				if r == None:
					z[-1].nextRight = None
					z = []
					l.append(None)
					continue
				if len(z) != 0:
					z[-1].nextRight = r
				z.append(r)
				if r.left != None:
					l.append(r.left)
				if r.right != None:
					l.append(r.right)
		p(root)


import collections
import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		levelLst = self.levelOrderTrav(root)
		for level in levelLst:
			prev = level[0]
			for nxt in level[1:]:
				prev.nextRight = nxt
				prev = nxt

	def levelOrderTrav(self, root):
		levelLst = []
		q = collections.deque()
		q.append(root)
		size = 1
		while size > 0:
			cur = size
			cur_lev = []
			for i in range(cur):
				node = q.popleft()
				cur_lev.append(node)
				size -= 1
				if node.left:
					size += 1
					q.append(node.left)
				if node.right:
					size += 1
					q.append(node.right)
			levelLst.append(cur_lev)
		return levelLst


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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

		def levelsum(root, count):
			if root == None:
				return
			if count in d:
				z = d.get(count)
				z.append(root)
				d[count] = z
			else:
				d[count] = [root]
			count = count + 1
			levelsum(root.left, count)
			levelsum(root.right, count)
		levelsum(root, count)
		for i in d:
			j = 0
			while j < len(d[i]) - 1:
				d[i][j].nextRight = d[i][j + 1]
				j = j + 1
			d[i][j].nextRight = None
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		que = [root]
		while que:
			l = []
			for i in range(len(que)):
				x = que.pop(0)
				if x.left is not None:
					que.append(x.left)
				if x.right is not None:
					que.append(x.right)
				l.append(x)
			for j in range(len(l) - 1):
				l[j].nextRight = l[j + 1]
		return root


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		q = []
		q.append(root)
		q.append(None)
		prev = None
		while q:
			cur = q.pop(0)
			if cur is None:
				prev = None
				if len(q) > 0:
					q.append(None)
			else:
				if prev:
					prev.nextRight = cur
				prev = cur
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if root is None:
			return
		arr = []
		arr.append(root)
		self.levelOrderRecur(arr)

	def levelOrderRecur(self, arr):
		if not arr:
			return
		for i in range(len(arr) - 1):
			arr[i].nextRight = arr[i + 1]
		arr[len(arr) - 1].nextRight = None
		newArr = []
		for node in arr:
			if node.left:
				newArr.append(node.left)
			if node.right:
				newArr.append(node.right)
		self.levelOrderRecur(newArr)


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		if root is None:
			return
		que = []
		que.append(root)
		while que:
			prev = None
			l = len(que)
			for i in range(l):
				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)


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def connect(self, root):
		que = [root]
		lst = []
		while len(que):
			n = len(que)
			l = []
			for i in range(n):
				temp = que.pop(0)
				l.append(temp)
				if temp.left:
					que.append(temp.left)
				if temp.right:
					que.append(temp.right)
			lst.append(l)
		for i in lst:
			for j in range(len(i)):
				if j == len(i) - 1:
					i[j].nextRight = None
				else:
					i[j].nextRight = i[j + 1]


from collections import defaultdict

class Solution:

	def connect(self, root):
		self.currentNodes = defaultdict(lambda : None)
		self.traverse(root, 0)
		return root

	def traverse(self, node, level):
		prevNode = self.currentNodes[level]
		if prevNode is not None:
			prevNode.nextRight = node
		self.currentNodes[level] = node
		if node.left:
			self.traverse(node.left, level + 1)
		if node.right:
			self.traverse(node.right, level + 1)
		return


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

	def lvl(self, root, l):
		q = []
		z = []
		q.append(root)
		while q != []:
			size = len(q)
			while size > 0:
				a = q.pop(0)
				z.append(a)
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
				size -= 1
			l.append(z)
			z = []
		return l

	def connect(self, root):
		l = self.lvl(root, [])
		for x in range(len(l)):
			for y in range(len(l[x]) - 1):
				l[x][y].nextRight = l[x][y + 1]
			l[x][-1].nextRight = None


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:
	dp = dict()

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

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:
	import sys
sys.setrecursionlimit(50000)

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
		self.nextRight = None
from collections import deque

class Solution:

	def connect(self, root):
		q = deque()
		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.popleft()


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Solution:

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


import sys
sys.setrecursionlimit(50000)

class Node:

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

class Solution:

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