Given a Linked List Representation of Complete Binary Tree. The task is to construct the Binary tree.
Note : The complete binary tree is represented as a linked list in a way where if root node is stored at position i, its left, and right children are stored at position 2*i+1, 2*i+2 respectively.
Example 1:
Input:
N = 5
K = 1->2->3->4->5
Output: 1 2 3 4 5
Explanation: The tree would look like
      1
    /   \
   2     3
 /  \
4   5
Now, the level order traversal of
the above tree is 1 2 3 4 5.
Example 2:
Input:
N = 5
K = 5->4->3->2->1
Output: 5 4 3 2 1
Explanation: The tree would look like
     5
   /  \
  4    3
 / \
2    1
Now, the level order traversal of
the above tree is 5 4 3 2 1.
Your Task:
The task is to complete the function convert() which takes head of linked list and root of the tree as the reference. The driver code prints the level order.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Note: H is the height of the tree and this space is used implicitly for recursion stack.
Constraints:
1 <= N <= 10^{5}
1 <= K_{i} <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: # User function Template for python3



'''

class ListNode:



    # Constructor to create a new node

    def __init__(self, data):

        self.data = data

        self.next = None





# Tree Node structure

class Tree:



    # Constructor to create a new node

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None



'''



#Function to make binary tree from linked list.

def convert(head):

  

    # code here



Solutions:
def convert(head):
	l = []
	i = 0
	while head:
		l.append((Tree(head.data), i))
		head = head.next
		i += 1
	root = ArrayToBST(l)
	return root

def ArrayToBST(arr):
	temp = arr[0][0]
	root = arr[0]
	length = len(arr)
	queue = [root]
	while queue:
		(root, index) = queue.pop(0)
		if 2 * index + 1 < length:
			root.left = arr[2 * index + 1][0]
			queue.append((root.left, 2 * index + 1))
		if 2 * index + 2 < length:
			root.right = arr[2 * index + 2][0]
			queue.append((root.right, 2 * index + 2))
	return temp


def convert(head):
	root = None
	if head != None:
		root = Tree(head.data)
		head = head.next
		root.next = None
	temp = head
	count = 0
	q = [root]
	while temp != None:
		count += 1
		temp = temp.next
	for i in range(count // 2):
		temp = q[0]
		q.pop(0)
		temp.left = Tree(head.data)
		head = head.next
		temp.left.next = None
		q.append(temp.left)
		temp.right = Tree(head.data)
		head = head.next
		temp.right.next = None
		q.append(temp.right)
	if count & 1 == 1:
		temp = q[0]
		q.pop(0)
		temp.left = Tree(head.data)
		head = head.next
		temp.left.next = None
	return root


def convert(head):
	root = Tree(head.data)
	q = []
	q.append(root)
	while q:
		node = q.pop(0)
		if head.next:
			head = head.next
			node.left = Tree(head.data)
			q.append(node.left)
		if head.next:
			head = head.next
			node.right = Tree(head.data)
			q.append(node.right)
	return root


def convert(head):
	q = []
	cur = head
	pk = Tree(None)
	while cur:
		q.append(cur.data)
		cur = cur.next

	def const(arr, i, n):
		root = None
		if i < n:
			root = Tree(arr[i])
			root.left = const(arr, 2 * i + 1, n)
			root.right = const(arr, 2 * i + 2, n)
		return root
	return const(q, 0, len(q))


def solve(lis, i, n):
	root = None
	if i < n:
		root = Tree(lis[i])
		root.left = solve(lis, 2 * i + 1, n)
		root.right = solve(lis, 2 * i + 2, n)
	return root

def convert(head):
	lis = []
	itr = head
	while itr:
		lis.append(itr.data)
		itr = itr.next
	return solve(lis, 0, len(lis))


def convert(head):
	if not head:
		return
	root = Tree(head.data)
	head = head.next
	queue = [root]
	while head:
		if not queue[0].left:
			queue[0].left = Tree(head.data)
			queue.append(queue[0].left)
		else:
			temp = queue.pop(0)
			temp.right = Tree(head.data)
			queue.append(temp.right)
		head = head.next
	return root


def convert(head):
	if head is None:
		return
	if head.next is None:
		return Tree(head.data)
	root = Tree(head.data)
	(q, pos, len1) = ([root], 0, 1)
	while pos < len1:
		top = q[pos]
		if head.next:
			head = head.next
			top.left = Tree(head.data)
			q.append(top.left)
			len1 += 1
		else:
			break
		if head.next:
			head = head.next
			top.right = Tree(head.data)
			q.append(top.right)
			len1 += 1
		else:
			break
		pos += 1
	return root


def convert(head):
	li = []
	temp = head
	while temp:
		li.append(temp.data)
		temp = temp.next
	li.reverse()
	print(*li)


from collections import deque

def convert(head):
	root = None
	q = deque()
	while head:
		node = Tree(head.data)
		if not root:
			root = node
			p = node
			left = True
		elif left:
			p.left = node
			left = False
			q.append(node)
		else:
			p.right = node
			q.append(node)
			left = True
			p = q.popleft()
		head = head.next
	return root


idx = -1.0

def convert(head):
	lst = []
	while head != None:
		lst.append(head.data)
		head = head.next
	root = _convert(lst, 0)
	return root

def _convert(lst, inx):
	if check(lst, inx):
		return None
	root = Tree(lst[inx])
	root.left = _convert(lst, 2 * inx + 1)
	root.right = _convert(lst, 2 * inx + 2)
	return root

def check(lst, inx):
	try:
		if lst[int(inx)]:
			return False
	except:
		return True


def convert(head):
	if head == None:
		return
	if head.next == None:
		return Tree(head.data)
	root = Tree(head.data)
	q = [root]
	temp = 0
	lenn = 1
	while temp < lenn:
		ele = q[temp]
		if head.next:
			head = head.next
			ele.left = Tree(head.data)
			q.append(ele.left)
			lenn += 1
		else:
			break
		if head.next:
			head = head.next
			ele.right = Tree(head.data)
			q.append(ele.right)
			lenn += 1
		else:
			break
		temp += 1
	return root


from collections import deque

def convert(head):
	if head == None:
		return None
	root = Tree(head.data)
	dq = deque()
	dq.append(root)
	head = head.next
	while len(dq) > 0 and head != None:
		temp = dq.popleft()
		if head != None:
			temp.left = Tree(head.data)
			dq.append(temp.left)
			head = head.next
		if head != None:
			temp.right = Tree(head.data)
			dq.append(temp.right)
			head = head.next
	return root


def helper(l, n, i):
	if i >= n:
		return None
	node = Tree(l[i])
	node.left = helper(l, n, 2 * i + 1)
	node.right = helper(l, n, 2 * i + 2)
	return node

def convert(head):
	l = []
	temp = head
	while temp:
		l.append(temp.data)
		temp = temp.next
	n = len(l)
	return helper(l, n, 0)


from collections import deque

def convert(head):
	g = []
	curr = head
	while curr:
		g.append(curr.data)
		curr = curr.next
	k = len(g)
	q = deque()
	root = Tree(g[0])
	q.append(root)
	i = 0
	while q:
		cu = q.popleft()
		if 2 * i + 1 < len(g):
			cu.left = Tree(g[2 * i + 1])
			q.append(cu.left)
		if 2 * i + 2 < k:
			cu.right = Tree(g[2 * i + 2])
			q.append(cu.right)
		i += 1
	return root


import collections

def convert(head):

	def bt(arr):
		q = collections.deque()
		root = Tree(arr[0])
		q.append(root)
		i = 0
		while q:
			cur = q.popleft()
			if 2 * i + 1 < len(arr):
				cur.left = Tree(arr[2 * i + 1])
				q.append(cur.left)
			if 2 * i + 2 < len(arr):
				cur.right = Tree(arr[2 * i + 2])
				q.append(cur.right)
			i += 1
		return root
	arr = []
	temp = head
	while temp:
		arr.append(temp.data)
		temp = temp.next
	ans = bt(arr)
	return ans


def convert(head):
	queue = [head]
	root = Tree(head.data)
	queue1 = [root]
	head = head.next
	while len(queue) > 0:
		x = queue.pop(0)
		y = queue1.pop(0)
		if head:
			y.left = Tree(head.data)
			queue.append(head)
			queue1.append(y.left)
			head = head.next
		if head:
			y.right = Tree(head.data)
			queue.append(head)
			queue1.append(y.right)
			head = head.next
	return root


def convert(head):
	arrT = [-1 for i in range(100001)]
	temp = head
	i = 0
	while temp != None:
		arrT[i] = temp.data
		i += 1
		temp = temp.next

	def constructBT(indx):
		if indx > 100000 or arrT[indx] == -1:
			return None
		node = Tree(arrT[indx])
		node.left = constructBT(2 * indx + 1)
		node.right = constructBT(2 * indx + 2)
		return node
	return constructBT(0)


from collections import deque

def levelorder(root, data):
	new_node = Tree(data)
	if not root:
		root = new_node
		return root
	q = deque([root])
	while q:
		node = q.popleft()
		if not node.left:
			node.left = new_node
			return root
		elif not node.right:
			node.right = new_node
			return root
		q.append(node.left)
		q.append(node.right)

def convert(head):
	if not head:
		return None
	root = Tree(head.data)
	head = head.next
	q = deque()
	q.append(root)
	while head:
		parent = q.popleft()
		if head:
			left_child = Tree(head.data)
			parent.left = left_child
			q.append(left_child)
			head = head.next
		if head:
			right_child = Tree(head.data)
			parent.right = right_child
			q.append(right_child)
			head = head.next
	return root


def convert(head):
	li = []
	cur = head
	while cur:
		ans = Tree(cur.data)
		li.append(ans)
		cur = cur.next
	n = len(li)
	for i in range(n // 2):
		if 2 * i + 1 < n:
			li[i].left = li[2 * i + 1]
		if 2 * i + 2 < n:
			li[i].right = li[2 * i + 2]
	return li[0]


from collections import deque

def convert(head):
	start = Tree(head.data)
	head = head.next
	queue = deque()
	queue.append(start)
	while head and head.next:
		root = queue.popleft()
		root.left = Tree(head.data)
		head = head.next
		queue.append(root.left)
		root.right = Tree(head.data)
		head = head.next
		queue.append(root.right)
	if head:
		queue[0].left = Tree(head.data)
	return start


def convert(head):
	if not head:
		return None
	root = Tree(head.data)
	head = head.next
	q = [root]
	while head:
		n = q.pop(0)
		n.left = Tree(head.data)
		q.append(n.left)
		head = head.next
		if head:
			n.right = Tree(head.data)
			head = head.next
			q.append(n.right)
	return root


from collections import deque

def convert(head):
	root = Tree(head.data)
	q = deque([root])
	curHead = head.next
	while curHead:
		cur = q.popleft()
		if curHead:
			cur.left = Tree(curHead.data)
			q.append(cur.left)
			curHead = curHead.next
		if curHead:
			cur.right = Tree(curHead.data)
			q.append(cur.right)
			curHead = curHead.next
	return root


def convert(head):

	def add(root, ind, nums):
		if not root:
			return
		(l, r) = (2 * ind + 1, 2 * ind + 2)
		if l < len(nums):
			root.left = Tree(nums[l])
		if r < len(nums):
			root.right = Tree(nums[r])
		add(root.left, l, nums)
		add(root.right, r, nums)
	cur = head
	nums = []
	while cur:
		nums.append(cur.data)
		cur = cur.next
	root = Tree(nums[0])
	add(root, 0, nums)
	return root


from collections import deque

def convert(head):
	root = None
	if not head:
		return root
	root = Tree(head.data)
	cur = head.next
	q = deque([root])
	while q:
		cur_node = q.popleft()
		if cur:
			cur_node.left = Tree(cur.data)
			q.append(cur_node.left)
			cur = cur.next
		if cur:
			cur_node.right = Tree(cur.data)
			q.append(cur_node.right)
			cur = cur.next
	return root


def convert(head):
	arr = []
	i = 0
	curr = head
	length = 0
	while curr != None:
		arr.append(Tree(curr.data))
		curr = curr.next
		length += 1
	curr = head
	i = 0
	root = arr[0]
	l = 2 * i + 1
	r = 2 * i + 2
	while l < n or r < n:
		if l < n:
			arr[i].left = arr[l]
		if r < n:
			arr[i].right = arr[r]
		i += 1
		l = 2 * i + 1
		r = 2 * i + 2
	return arr[0]


def convert(head):
	queue = []
	if head is None:
		root = Tree(None)
		return
	root = Tree(head.data)
	queue.append(root)
	head = head.next
	while head:
		parentNode = queue.pop(0)
		parentNode.left = Tree(head.data)
		queue.append(parentNode.left)
		head = head.next
		if head:
			parentNode.right = Tree(head.data)
			head = head.next
			queue.append(parentNode.right)
	return root


def convert(head):
	Tre = None
	L = None
	R = None
	root = None
	List = []
	while head:
		List.append(head.data)
		head = head.next
	i = 0
	return dfs(root, List, i)

def dfs(root, List, i):
	if i < len(List):
		N = Tree(List[i])
		N.left = dfs(root, List, 2 * i + 1)
		N.right = dfs(root, List, 2 * i + 2)
		return N


def convert(head):
	arr = []
	while head != None:
		arr.append(head)
		head = head.next
	arr = [Tree(x.data) for x in arr]
	for x in range(len(arr) + 1):
		if 2 * x + 1 >= len(arr):
			continue
		arr[x].left = arr[2 * x + 1]
		if 2 * x + 2 >= len(arr):
			continue
		arr[x].right = arr[2 * x + 2]
	return arr[0]


def binary_tree(arr, i, n):
	if i >= n:
		return None
	node = Tree(arr[i])
	node.left = binary_tree(arr, 2 * i + 1, n)
	node.right = binary_tree(arr, 2 * i + 2, n)
	return node

def convert(head):
	arr = list()
	temp = head
	while temp:
		arr.append(temp.data)
		temp = temp.next
	return binary_tree(arr, 0, len(arr))


def convert(head):
	root = None
	if head is None:
		return root
	root = Tree(head.data)
	curLL = head.next
	q = []
	q.append(root)
	while len(q) > 0:
		n = len(q)
		for i in range(n):
			if curLL is None:
				break
			node = q.pop(0)
			newNode = Tree(curLL.data)
			node.left = newNode
			q.append(newNode)
			curLL = curLL.next
			if curLL:
				newNode = Tree(curLL.data)
				node.right = newNode
				q.append(newNode)
				curLL = curLL.next
		if curLL is None:
			break
	return root


import collections

def convert(head):
	if head is None:
		return head
	root = Tree(head.data)
	x = collections.deque()
	x.append(root)
	curr = head.next
	while curr:
		n = x.popleft()
		n.left = Tree(curr.data)
		x.append(n.left)
		curr = curr.next
		if curr:
			n.right = Tree(curr.data)
			x.append(n.right)
			curr = curr.next
	return root


def func(pos, head, ans):
	if pos >= len(ans):
		return None
	LinkNode = ans[pos]
	TreeNode = Tree(LinkNode)
	TreeNode.left = func(pos * 2 + 1, head, ans)
	TreeNode.right = func(pos * 2 + 2, head, ans)
	return TreeNode

def convert(head):
	Node = head
	ans = []
	while Node:
		ans.append(Node.data)
		Node = Node.next
	return func(0, head, ans)


def convert(head):
	A = []
	curr = head
	while curr:
		A.append(curr.data)
		curr = curr.next

	def helper(i, n, A):
		if i >= n or i < 0:
			return
		root = Tree(A[i])
		root.left = helper(i * 2 + 1, n, A)
		root.right = helper(i * 2 + 2, n, A)
		return root
	return helper(0, len(A), A)


class Tree:

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

def convert(head):
	h = head
	d = {}
	i = head.next
	while i and i.next:
		d[head] = [i, i.next]
		head = head.next
		i = i.next.next
	if i:
		d[head] = [i]
	if not d:
		return Tree(head.data)
	make_tree(h, d)
	return h

def make_tree(root, d):
	if root:
		if root not in d:
			root.left = None
			root.right = None
			return
		root.left = d[root][0]
		root.right = None if len(d[root]) == 1 else d[root][1]
		make_tree(root.left, d)
		make_tree(root.right, d)


def convert(head):
	if not head:
		return
	if head.next is None:
		return Tree(head.data)
	root = Tree(head.data)
	head = head.next
	q = [root]
	(pos, l) = (0, 1)
	while q:
		sz = len(q)
		for i in range(sz):
			curr = q.pop(0)
			if head:
				curr.left = Tree(head.data)
				q.append(curr.left)
				head = head.next
			else:
				break
			if head:
				curr.right = Tree(head.data)
				q.append(curr.right)
				head = head.next
			else:
				break
		if not head:
			break
	return root


def convert(head):
	q = []
	if head is None:
		root = None
		return
	root = Tree(head.data)
	q.append(root)
	head = head.next
	while head:
		parent = q.pop(0)
		leftChild = None
		rightChild = None
		leftChild = Tree(head.data)
		q.append(leftChild)
		head = head.next
		if head:
			rightChild = Tree(head.data)
			q.append(rightChild)
			head = head.next
		parent.left = leftChild
		parent.right = rightChild
	return root


import collections

def convert(head):
	root = Tree(head.data)
	queue = collections.deque([root])
	cur = head.next
	while cur:
		curTNode = queue.pop()
		curTNode.left = Tree(cur.data)
		queue.appendleft(curTNode.left)
		cur = cur.next
		if cur:
			curTNode.right = Tree(cur.data)
			queue.appendleft(curTNode.right)
			cur = cur.next
	return root


def convert(head):
	n = head
	q = []
	if n != None:
		q.append(Tree(n.data))
		n = n.next
	parent = None
	root = None
	while n != None:
		if parent == None:
			parent = q.pop(0)
			root = parent
		else:
			parent = q.pop(0)
		lchild = None
		rchild = None
		lchild = Tree(n.data)
		q.append(lchild)
		n = n.next
		if n != None:
			rchild = Tree(n.data)
			q.append(rchild)
			n = n.next
		if lchild != None:
			parent.left = lchild
		if rchild != None:
			parent.right = rchild
	if root == None and head != None:
		root = Tree(head.data)
	return root


def convert(head):
	temp = []
	curr = head
	while curr:
		node = Tree(curr.data)
		node.left = None
		node.right = None
		temp.append(node)
		curr = curr.next
	n = len(temp)
	root = temp[0]
	for i in range(n // 2):
		if 2 * i + 1 < n:
			temp[i].left = temp[2 * i + 1]
		if 2 * i + 2 < n:
			temp[i].right = temp[2 * i + 2]
	return root


def convert(head):
	q = []
	curr = head
	while curr:
		q.append(curr.data)
		curr = curr.next

	def construct(arr, i, n):
		root = None
		if i < n:
			root = Tree(arr[i])
			root.left = construct(arr, 2 * i + 1, n)
			root.right = construct(arr, 2 * i + 2, n)
		return root
	return construct(q, 0, len(q))


def convert(head):
	root = None
	temp = None
	if head is None:
		return None
	root = Tree(head.data)
	temp = root
	while head.next:
		head = head.next
		root.left = Tree(head.data)
		if head.next:
			head = head.next
			root.right = Tree(head.data)
		root = root.left
	return temp


def convert(head):
	l = []
	p = head
	while p:
		l.append(p.data)
		p = p.next
	root = Tree(l[0])
	i = 1
	q = [root]
	while i < len(l) and q:
		t = l[i]
		s = q.pop()
		s.left = Tree(t)
		q.append(s.left)
		i += 1
		if i >= len(l):
			break
		t = l[i]
		s.right = Tree(t)
		q.append(s.right)
		i += 1
	return root


def convert(head):
	n = head
	if n == None:
		return None
	q = []
	q.append(Tree(n.data))
	n = n.next
	count = 0
	while n != None:
		parent = q.pop(0)
		if count == 0:
			root = parent
		parent.left = Tree(n.data)
		q.append(parent.left)
		n = n.next
		count += 1
		if n != None:
			parent.right = Tree(n.data)
			q.append(parent.right)
		else:
			break
		n = n.next
	if count == 0:
		root = q[0]
	return root


from collections import deque

def convert(head):
	if head is None:
		return None
	que = deque()
	tree = Tree(head.data)
	que.append(tree)
	head = head.next
	while len(que) > 0:
		node = que.popleft()
		leftNode = None
		rightNode = None
		if head:
			leftNode = Tree(head.data)
			que.append(leftNode)
			head = head.next
		if head:
			rightNode = Tree(head.data)
			que.append(rightNode)
			head = head.next
		node.left = leftNode
		node.right = rightNode
	return tree


def convert(head):

	def rev(head):
		prev = None
		cur = head
		while cur != None:
			next = cur.next
			cur.next = prev
			prev = cur
			cur = next
		return prev
	q = []
	if head == None:
		return None
	root = Tree(head.data)
	q.append(root)
	head = head.next
	while head:
		p = q.pop(0)
		lefty = Tree(head.data)
		head = head.next
		q.append(lefty)
		righty = None
		if head:
			righty = Tree(head.data)
			head = head.next
			q.append(righty)
		p.left = lefty
		p.right = righty
	return root


from collections import deque

def convert(head):
	q = deque()
	new = Tree(head.data)
	head = head.next
	q.append(new)
	while head:
		prt = q.popleft()
		rightchild = None
		leftchild = None
		leftchild = Tree(head.data)
		q.append(leftchild)
		if head.next:
			head = head.next
			rightchild = Tree(head.data)
			q.append(rightchild)
		prt.left = leftchild
		prt.right = rightchild
		head = head.next
	return new


def convert(head):
	stack = []
	while head:
		stack.append(Tree(head.data))
		head = head.next
	n = len(stack)
	for i in range(n):
		if 2 * i + 1 < n:
			stack[i].left = stack[2 * i + 1]
		if 2 * i + 2 < n:
			stack[i].right = stack[2 * i + 2]
	return stack[0]


def convert(head):
	if head == None:
		root = None
		return
	root = Tree(head.data)
	head = head.next
	queue = []
	queue.append(root)
	while head:
		node = queue.pop(0)
		lch = None
		rch = None
		lch = Tree(head.data)
		queue.append(lch)
		head = head.next
		if head:
			rch = Tree(head.data)
			queue.append(rch)
			head = head.next
		node.left = lch
		node.right = rch
	return root


def convert(head):
	if not head:
		return
	root = Tree(head.data)
	ret = root
	q = []
	q.append(root)
	head = head.next
	while head:
		tmp = q[0]
		root = Tree(head.data)
		if not tmp.left:
			tmp.left = root
			q.append(root)
		else:
			tmp.right = root
			q.append(root)
			q.pop(0)
		head = head.next
	return ret


from collections import deque

def convert(head):
	root = Tree(head.data)
	q = deque()
	q.append(root)
	head = head.next
	while head:
		nd = q.popleft()
		nd.left = Tree(head.data)
		q.append(nd.left)
		head = head.next
		if head == None:
			break
		nd.right = Tree(head.data)
		q.append(nd.right)
		head = head.next
	return root


class Tree:

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

class Solution:

	def __init__(self, node_values) -> None:
		self.node_values = node_values
		self.size = len(self.node_values)

	def makeTree(self, idx):
		if idx >= self.size:
			return None
		root = Tree(self.node_values[idx])
		root.left = self.makeTree((idx << 1) + 1)
		root.right = self.makeTree((idx << 1) + 2)
		return root

def convert(head):
	node_values = []
	tmp = head
	while tmp:
		node_values.append(tmp.data)
		tmp = tmp.next
	sol = Solution(node_values)
	return sol.makeTree(0)


from collections import deque

def convert(head):
	if not head:
		return None
	root = Tree(head.data)
	(curr, q) = (head.next, deque([root]))
	while q:
		node = q.popleft()
		if curr:
			node.left = Tree(curr.data)
			curr = curr.next
			q.append(node.left)
		if curr:
			node.right = Tree(curr.data)
			curr = curr.next
			q.append(node.right)
	return root


from collections import deque

def convert(head):
	if head:
		q = deque()
		root = Tree(head.data)
		q.append(root)
		tmp = head.next
		while tmp and q:
			n = len(q)
			i = 0
			max_child = 2 ** n
			while tmp and i < max_child:
				node = Tree(tmp.data)
				if i % 2 == 0:
					parent = q.popleft()
					parent.left = node
				else:
					parent.right = node
				q.append(node)
				i += 1
				tmp = tmp.next
		return root


def convert(head):
	arr = []
	while head:
		arr.append(head.data)
		head = head.next
	dic = dict()
	root = Tree(arr[0])
	dic[0] = root
	node = root
	n = len(arr)
	for i in range(n):
		if 2 * i + 1 < n:
			dic[i].left = Tree(arr[2 * i + 1])
			dic[2 * i + 1] = dic[i].left
		if 2 * i + 2 < n:
			dic[i].right = Tree(arr[2 * i + 2])
			dic[2 * i + 2] = dic[i].right
	return root


def convert(head):
	if head is None:
		return
	if head.next is None:
		return Tree(head.data)
	q = [Tree(head.data)]
	root = None
	l_child = head.next
	r_child = head.next.next
	while len(q):
		temp = q.pop(0)
		if root is None:
			l_child_node = Tree(l_child.data)
			temp.left = l_child_node
			q.append(l_child_node)
			if r_child:
				r_child_node = Tree(r_child.data)
				temp.right = r_child_node
				q.append(r_child_node)
			root = temp
		else:
			if l_child and l_child.next and l_child.next.next:
				l_child = l_child.next.next
				l_child_node = Tree(l_child.data)
				temp.left = l_child_node
				q.append(l_child_node)
			if r_child and r_child.next and r_child.next.next:
				r_child = r_child.next.next
				r_child_node = Tree(r_child.data)
				temp.right = r_child_node
				q.append(r_child_node)
	return root


def convert(head):
	if not head:
		return None
	root = Tree(head.data)
	q = [root]
	head = head.next
	while q and head:
		temp = q.pop(0)
		if not temp:
			break
		temp.left = None if not head else Tree(head.data)
		head = head.next
		q.append(temp.left)
		temp.right = None if not head else Tree(head.data)
		if not head:
			break
		head = head.next
		q.append(temp.right)
	return root


def convert(head):
	temp = head
	while temp:
		temp.data = Tree(temp.data)
		temp = temp.next
	temp = head
	temp2 = head.next
	while temp2:
		temp.data.left = temp2.data
		temp2 = temp2.next
		if temp2:
			temp.data.right = temp2.data
			temp2 = temp2.next
		temp = temp.next
	return head.data


def convert(head):
	q = []
	if head == None:
		root = None
		return
	root = Tree(head.data)
	head = head.next
	q.append(root)
	while head:
		parent = q.pop(0)
		leftc = None
		rightc = None
		leftc = Tree(head.data)
		head = head.next
		q.append(leftc)
		if head:
			rightc = Tree(head.data)
			head = head.next
			q.append(rightc)
		parent.left = leftc
		parent.right = rightc
	return root


def convert(head):
	root = Tree(head.data)
	queue = []
	queue.append(root)
	head = head.next
	while head:
		curr = queue.pop(0)
		curr.left = Tree(head.data)
		queue.append(curr.left)
		head = head.next
		if head:
			curr.right = Tree(head.data)
			queue.append(curr.right)
			head = head.next
	return root


from collections import *

def convert(head):
	if not head:
		return None
	root = Tree(head.data)
	head = head.next
	queue = deque()
	queue.append(root)
	while head:
		(left, right) = (None, None)
		parent = queue.popleft()
		left = Tree(head.data)
		queue.append(left)
		head = head.next
		if head:
			right = Tree(head.data)
			head = head.next
			queue.append(right)
		parent.left = left
		parent.right = right
	return root


def convert(head):
	current = head
	if not head:
		return
	if current.next is None:
		root = Tree(current.data)
		return root
	root = Tree(current.data)
	current_tree = root
	current = current.next
	while current:
		if current_tree.left and current_tree.right:
			current_tree = current_tree.left
		if not current_tree.left:
			current_tree.left = Tree(current.data)
		elif not current_tree.right:
			current_tree.right = Tree(current.data)
		current = current.next
	return root


from collections import deque

def convert(head):
	if head == None:
		return
	root = Tree(head.data)
	if head.next == None:
		return root
	q = deque()
	q.append(root)
	while head.next != None:
		head = head.next
		parent = q.popleft()
		leftnode = rightnode = None
		leftnode = Tree(head.data)
		q.append(leftnode)
		if head.next != None:
			head = head.next
			rightnode = Tree(head.data)
			q.append(rightnode)
		parent.left = leftnode
		parent.right = rightnode
	return root


def convert(head):
	if head == None:
		return
	else:
		tree_nodes = []
		curr = head
		while curr:
			temp = Tree(curr.data)
			tree_nodes.append(temp)
			curr = curr.next
		i = 0
		n = len(tree_nodes)
		while i < n:
			node = tree_nodes[i]
			node.left = tree_nodes[2 * i + 1] if 2 * i + 1 < n else None
			node.right = tree_nodes[2 * i + 2] if 2 * i + 2 < n else None
			i += 1
		return tree_nodes[0]


def convert(head):
	res = []
	while head:
		res.append(Tree(head.data))
		head = head.next
	i = 0
	n = len(res)
	while i <= n // 2:
		node = res[i]
		if 2 * i + 1 < n:
			node.left = res[2 * i + 1]
		if 2 * i + 2 < n:
			node.right = res[2 * i + 2]
		i += 1
	return res[0]


def convert(head):
	arr = []
	while head:
		arr.append(head.data)
		head = head.next
	n = len(arr)
	noderep = {}
	root = Tree(arr[0])
	noderep[0] = root
	i = 0
	while i < n:
		parent = noderep[i]
		if 2 * i + 1 >= n:
			break
		else:
			child1 = Tree(arr[2 * i + 1])
			noderep[2 * i + 1] = child1
			parent.left = child1
		if 2 * i + 2 >= n:
			break
		else:
			child2 = Tree(arr[2 * i + 2])
			noderep[2 * i + 2] = child2
			parent.right = child2
		i += 1
	return root


from collections import deque

def convert(head):

	def using_preorder():

		def solve(l, i):
			if i >= len(l):
				return None
			root = Tree(l[i])
			root.left = solve(l, 2 * i + 1)
			root.right = solve(l, 2 * i + 2)
			return root
		l = []
		temp = head
		while temp:
			l.append(temp.data)
			temp = temp.next
		return solve(l, 0)

	def using_levelorder():
		q = deque()
		temp = head
		root = Tree(head.data)
		temp = temp.next
		if temp:
			root.left = Tree(temp.data)
			q.append(root.left)
			temp = temp.next
			if temp:
				root.right = Tree(temp.data)
				q.append(root.right)
				temp = temp.next
		while temp:
			node = q.popleft()
			left = temp.data
			right = None
			temp = temp.next
			if temp:
				right = temp.data
				temp = temp.next
			node.left = Tree(left)
			q.append(node.left)
			if right is not None:
				node.right = Tree(right)
				q.append(node.right)
		return root
	return using_levelorder()


def convert(head):
	res = []
	while head:
		res.append(head.data)
		head = head.next
	res[0] = Tree(res[0])
	root = res[0]
	f = 0
	for i in range(1, len(res)):
		if f == 0:
			res[(i - 1) // 2].left = Tree(res[i])
			res[i] = res[(i - 1) // 2].left
		else:
			res[(i - 1) // 2].right = Tree(res[i])
			res[i] = res[(i - 1) // 2].right
		f = 1 - f
	return root


def convert(head):

	def solve(l, i):
		if i >= len(l):
			return None
		root = Tree(l[i])
		root.left = solve(l, 2 * i + 1)
		root.right = solve(l, 2 * i + 2)
		return root
	l = []
	temp = head
	while temp:
		l.append(temp.data)
		temp = temp.next
	return solve(l, 0)