Given an array of size N that can be used to represents a tree. The array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of Binary Tree from this array representation.
Note: If two elements have the same parent, the one that appears first in the array will be the left child and the other is the right child. 
Example 1:
Input:
N = 7
parent[] = {-1,0,0,1,1,3,5}
Output: 0 1 2 3 4 5 6
Explanation: the tree generated
will have a structure like 
          0
        /   \
       1     2
      / \
     3   4
    /
   5
 /
6
Example 2:
Input:
N = 3
parent[] = {2, 0, -1}
Output: 2 0 1
Explanation: the tree generated will
have a sturcture like
               2
             /   
            0      
          /   
         1     
Your Task:
You don't need to read input or print anything. The task is to complete the function createTree() which takes 2 arguments parent[] and N and returns the root node of the constructed tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3





'''

# A node structure

class Node:

    # A utility function to create a new node

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

'''

class Solution:

    #Function to construct binary tree from parent array.

    def createTree(self,parent,N):

        # your code here

    

Solutions:
class Solution:

	def createTree(self, parent, N):
		pos = []
		for i in range(0, N):
			x = Node(i)
			pos.append(x)
		for i in range(0, N):
			if parent[i] == -1:
				root = pos[i]
			elif pos[parent[i]].left is None:
				pos[parent[i]].left = pos[i]
			else:
				pos[parent[i]].right = pos[i]
		return root


def createNode(parent, i, created, root):
	if created[i] is not None:
		return
	created[i] = Node(i)
	if parent[i] == -1:
		root[0] = created[i]
		return
	if created[parent[i]] is None:
		createNode(parent, parent[i], created, root)
	p = created[parent[i]]
	if p.left is None:
		p.left = created[i]
	else:
		p.right = created[i]

class Solution:

	def createTree(self, parent, n):
		n = len(parent)
		created = [None for i in range(n + 1)]
		root = [None]
		for i in range(n):
			createNode(parent, i, created, root)
		return root[0]


class Solution:

	def createTree(self, parent, N):
		from collections import deque
		d = {}
		q = deque()
		ans = Node(-1)
		temp = ans
		for i in range(N):
			if parent[i] == -1:
				temp.left = Node(i)
				q.append(temp.left)
				continue
			elif parent[i] in d:
				d[parent[i]].append(i)
			else:
				d[parent[i]] = [i]
		while q:
			p = q.popleft()
			if p.key in d:
				for el in d[p.key]:
					if not p.left:
						temp = p
						temp.left = Node(el)
						temp = temp.left
						q.append(temp)
					elif not p.right:
						temp = p
						temp.right = Node(el)
						temp = temp.right
						q.append(temp)
		return ans.left


class Solution:

	def createTree(self, parent, N):
		mydict = dict()
		for i in range(N):
			mydict[i] = Node(i)
		root = Node(None)
		for i in range(N):
			if parent[i] == -1:
				root = mydict[i]
			elif mydict[parent[i]].left == None:
				mydict[parent[i]].left = mydict[i]
			else:
				mydict[parent[i]].right = mydict[i]
		return root


class Solution:

	def createTree(self, parent, N):
		dnew = {}
		root = None
		temp = None
		for k in range(0, N):
			if parent[k] == -1:
				root = Node(k)
				dnew[k] = root
			else:
				dnew[k] = Node(k)
		for k in range(0, N):
			if parent[k] != -1:
				temp = dnew[parent[k]]
				if temp.left is None:
					temp.left = dnew[k]
				else:
					temp.right = dnew[k]
		return root


class Solution:

	def createTree(self, parent, n):
		ref = []
		for i in range(0, n):
			t = Node(i)
			ref.append(t)
		for i in range(0, n):
			if parent[i] == -1:
				root = ref[i]
			elif ref[parent[i]].left is None:
				ref[parent[i]].left = ref[i]
			else:
				ref[parent[i]].right = ref[i]
		return root


class Solution:

	def createTree(self, p, n):
		d = dict()
		root = None
		for i in range(n):
			d[i] = Node(i)
		for i in range(n):
			if p[i] == -1:
				root = d[i]
			elif d[p[i]].left == None:
				d[p[i]].left = d[i]
			else:
				d[p[i]].right = d[i]
		return root


from typing import List

class Solution:

	def createTree(self, parent, N):
		if not N:
			return None
		nodemap = defaultdict(list)
		for i in range(N):
			nodemap[parent[i]].append(i)

		def find_nodes(p: List[int], node: Node):
			nonlocal N, nodemap
			if not nodemap[node.key]:
				return
			c = nodemap[node.key]
			count = len(c)
			if count > 0:
				node.left = Node(c[0])
				find_nodes(p, node.left)
			if count > 1:
				node.right = Node(c[1])
				find_nodes(p, node.right)
			return
		pnode = Node(nodemap[-1][0])
		find_nodes(parent, pnode)
		return pnode


from collections import deque
from collections import defaultdict

class Solution:

	def createTree(self, parent, N):
		d = defaultdict(list)
		for i in range(N):
			if parent[i] in d:
				d[parent[i]] += [i]
			else:
				d[parent[i]] = [i]
		root = Node(d[-1][0])
		q = deque()
		q.append(root)
		while q:
			k = q.popleft()
			t = d[k.key]
			for i in range(len(t)):
				if i == 0:
					k.left = Node(t[i])
					q.append(k.left)
				else:
					k.right = Node(t[i])
					q.append(k.right)
		return root


class Solution:

	def createTree(self, parent, N):
		(d, root) = ({}, None)
		for i in range(n):
			node = Node(i)
			if parent[i] == -1:
				root = node
			d[i] = node
		for i in range(n):
			if parent[i] == -1:
				continue
			child = i
			parents = d[parent[i]]
			if not parents.left:
				parents.left = d[i]
			elif not parents.right:
				parents.right = d[i]
		return root


class Solution:

	def createTree(self, parent, N):
		nodes = [0] * N
		for i in range(N):
			nodes[i] = Node(i)
		for i in range(N):
			if parent[i] == -1:
				root = nodes[i]
			elif nodes[parent[i]].left == None:
				nodes[parent[i]].left = nodes[i]
			else:
				nodes[parent[i]].right = nodes[i]
		return root


class Solution:

	def createTree(self, parent, N):
		from collections import defaultdict
		d1 = defaultdict(list)
		for i in range(N):
			d1[parent[i]].append(i)
		root = Node(d1[-1][0])
		que = [root]
		while que:
			r = que.pop(0)
			if r.key in d1:
				if len(d1[r.key]) == 1:
					nn = Node(d1[r.key][0])
					que.append(nn)
					r.left = nn
				else:
					nn = Node(d1[r.key][0])
					que.append(nn)
					r.left = nn
					nn = Node(d1[r.key][1])
					que.append(nn)
					r.right = nn
		return root


class Solution:

	def createTree(self, parent, N):
		dic = {}
		for i in range(N):
			Nod = Node(i)
			dic[i] = Nod
		for i in range(N):
			if parent[i] == -1:
				ans = dic[i]
			elif dic[parent[i]].left == None:
				dic[parent[i]].left = dic[i]
			else:
				dic[parent[i]].right = dic[i]
		return ans


class Solution:

	def createTree(self, parent, N):
		dict = {}
		ans = None
		for i in range(N):
			node = Node(i)
			dict[i] = node
		for i in range(N):
			if parent[i] == -1:
				ans = dict[i]
			elif dict[parent[i]].left == None:
				dict[parent[i]].left = dict[i]
			else:
				dict[parent[i]].right = dict[i]
		return ans


class Solution:

	def createTree(self, parent, N):
		dct = dict()
		for i in range(0, N):
			dct[i] = Node(0)
		root = None
		for i in range(0, N):
			dct[i].key = i
			if parent[i] == -1:
				root = dct[i]
			elif dct[parent[i]].left is None:
				dct[parent[i]].left = dct[i]
			else:
				dct[parent[i]].right = dct[i]
		return root


from collections import defaultdict as dd

class Solution:

	def createTree(self, parent, N):
		edges = dd(lambda : [])
		for i in range(N):
			edges[parent[i]].append(i)
		start = Node(edges[-1][0])
		stack = [start]
		while stack:
			root = stack.pop()
			if len(edges[root.key]) == 1:
				root.left = Node(edges[root.key][0])
				stack.append(root.left)
			if len(edges[root.key]) == 2:
				root.left = Node(edges[root.key][0])
				root.right = Node(edges[root.key][1])
				stack.append(root.left)
				stack.append(root.right)
		return start


class Solution:

	def createTree(self, parent, N):
		map_ = {}
		if N == 0:
			return Node
		match = -1
		for i in range(N):
			if parent[i] == -1:
				match = i
				root = Node(i)
				map_[i] = root
		for i in range(0, N):
			if i == match:
				continue
			if map_.get(i, False):
				node = map_[i]
			else:
				node = Node(i)
			if map_.get(parent[i], False):
				parent_node = map_[parent[i]]
				if not parent_node.left:
					parent_node.left = node
				else:
					parent_node.right = node
				map_[i] = node
			else:
				parent_node = Node(parent[i])
				parent_node.left = node
				map_[parent[i]] = parent_node
				map_[i] = node
		return root


class Solution:

	def createTree(self, parent, N):
		ref = []
		for i in range(N):
			node = Node(i)
			ref.append(node)
		root = None
		for i in range(N):
			if parent[i] == -1:
				root = ref[i]
			elif ref[parent[i]].left is None:
				ref[parent[i]].left = ref[i]
			else:
				ref[parent[i]].right = ref[i]
		return root

	def breadthFirstTraversal(self, nodes):
		new_nodes = []
		for node in nodes:
			if node is not None:
				print(node.key, end=' ')
				if node.left is not None:
					new_nodes.append(node.left)
				if node.right is not None:
					new_nodes.append(node.right)
		if len(new_nodes) > 0:
			self.breadthFirstTraversal(new_nodes)


class Solution:

	def createTree(self, parent, N):
		d = {}
		for i in range(0, len(parent)):
			if i not in d:
				n = Node(i)
				d[i] = n
			if parent[i] == -1:
				d[-1] = d[i]
				continue
			if parent[i] not in d:
				p = Node(parent[i])
				d[parent[i]] = p
			if d[parent[i]].left == None:
				d[parent[i]].left = d[i]
			else:
				d[parent[i]].right = d[i]
		return d[-1]


class Solution:

	def createTree(self, parent, N):
		root = None
		d = {}
		for i in range(N):
			if i not in d:
				d[i] = Node(i)
		root = None
		for i in range(N):
			if parent[i] == -1:
				root = d[i]
			elif d[parent[i]].left is None:
				d[parent[i]].left = d[i]
			elif d[parent[i]].right is None:
				d[parent[i]].right = d[i]
		return root


class Solution:

	def createTree(self, parent, N):
		tree = [Node(-1) for i in range(N)]
		root = None
		for i in range(N):
			if parent[i] == -1:
				root = tree[i]
				root.key = i
				continue
			par = tree[parent[i]]
			node = tree[i]
			node.key = i
			if not par.left:
				par.left = node
			else:
				par.right = node
			tree[i] = node
		return root


class Solution:

	def createTree(self, parent, N):
		v = []
		for i in range(N):
			temp = Node(i)
			v.append(temp)
		root = None
		for i in range(N):
			if parent[i] == -1:
				root = v[i]
				continue
			if v[parent[i]].left == None:
				v[parent[i]].left = v[i]
			else:
				v[parent[i]].right = v[i]
		return root


class Solution:

	def createTree(self, parent, N):
		root = None
		nodes = [Node(i) for i in range(N)]
		for i in range(N):
			if parent[i] == -1:
				root = nodes[i]
			else:
				p = nodes[parent[i]]
				if not p.left:
					p.left = nodes[i]
				else:
					p.right = nodes[i]
		return root


class Solution:

	def createTree(self, parent, N):
		ans = [Node(i) for i in range(N)]
		child = [0 for i in range(N)]
		root = 0
		for i in range(N):
			p = parent[i]
			if p == -1:
				root = i
				continue
			if child[p]:
				ans[p].right = ans[i]
			else:
				ans[p].left = ans[i]
				child[p] = 1
		return ans[root]


class Solution:

	def createTree(self, parent, N):
		a1 = {}
		for i in range(len(parent)):
			a1[i] = Node(i)
		for i in range(len(parent)):
			if parent[i] != -1:
				if a1[parent[i]].left == None:
					a1[parent[i]].left = a1[i]
				else:
					a1[parent[i]].right = a1[i]
		for i in range(len(parent)):
			if parent[i] == -1:
				return a1[i]


from collections import deque

class Solution:

	def createTree(self, parent, N):
		root = None
		leftchild = {}
		rightchild = {}
		for i in range(N):
			if parent[i] == -1:
				root = Node(i)
			elif parent[i] not in leftchild:
				leftchild[parent[i]] = i
			else:
				rightchild[parent[i]] = i
		q = deque([root])
		while q:
			cur = q.popleft()
			if cur.key in leftchild:
				cur.left = Node(leftchild[cur.key])
				q.append(cur.left)
			if cur.key in rightchild:
				cur.right = Node(rightchild[cur.key])
				q.append(cur.right)
		return root


class Solution:

	def createTree(self, parent, N):
		nodes = [Node(n) for n in range(N)]
		root = None
		for i in range(N):
			if parent[i] == -1:
				root = nodes[i]
			elif not nodes[parent[i]].left:
				nodes[parent[i]].left = nodes[i]
			elif not nodes[parent[i]].right:
				nodes[parent[i]].right = nodes[i]
		return root


import collections

class Solution:

	def createTree(self, parent, N):
		lc = {}
		rc = {}
		root = None
		for i in range(len(parent)):
			if parent[i] == -1:
				root = Node(i)
			elif parent[i] not in lc:
				lc[parent[i]] = i
			else:
				rc[parent[i]] = i
		q = collections.deque([root])
		while q:
			cur = q.popleft()
			if cur.key in lc:
				cur.left = Node(lc[cur.key])
				q.append(cur.left)
			if cur.key in rc:
				cur.right = Node(rc[cur.key])
				q.append(cur.right)
		return root


class Solution:

	def createTree(self, arr, n):
		idx_nd = dict()
		for i in range(n):
			idx_nd[i] = Node(i)
		head = None
		for i in range(n):
			cur = idx_nd.get(arr[i], -1)
			if arr[i] == -1:
				head = idx_nd[i]
				continue
			if not cur.left:
				cur.left = idx_nd[i]
			else:
				cur.right = idx_nd[i]
		return head


class Solution:

	def createTree(self, parent, n):
		adj = {}
		rootNode = -1
		for i in range(0, len(parent)):
			if parent[i] == -1:
				rootNode = i
			elif parent[i] not in adj:
				adj[parent[i]] = [i]
			else:
				adj[parent[i]].append(i)

		def construct(rootNode):
			if rootNode not in adj:
				return Node(rootNode)
			root = Node(rootNode)
			root.left = construct(adj[rootNode][0])
			if len(adj[rootNode]) > 1:
				root.right = construct(adj[rootNode][1])
			return root
		return construct(rootNode)


class Solution:

	def get(self, nodes, val):
		if nodes[val] == None:
			nodes[val] = Node(val)
		return nodes[val]

	def createTree(self, parent, N):
		if N == 1:
			return Node(0)
		root = None
		nodes = [None] * N
		for i in range(N):
			child = self.get(nodes, i)
			if parent[i] == -1:
				root = child
			else:
				father = self.get(nodes, parent[i])
				if not father.left:
					father.left = child
				else:
					father.right = child
		return root


class Solution:

	def createTree(self, parent, N):
		root = None
		arr = []
		for i in range(N):
			arr.append(Node(i))
		for i in range(N):
			p = parent[i]
			if p == -1:
				root = arr[i]
			else:
				pNode = arr[p]
				if pNode is not None:
					if not pNode.left:
						pNode.left = arr[i]
					else:
						pNode.right = arr[i]
		return root


class Solution:

	def createTree(self, parent, N):
		mp = {}
		for i in range(N):
			temp = Node(i)
			mp[i] = temp
		root = None
		for i in range(N):
			if parent[i] == -1:
				root = mp[i]
			else:
				t = mp[parent[i]]
				if t.left is None:
					t.left = mp[i]
				elif t.right is None:
					t.right = mp[i]
		return root


class Solution:

	def createTree(self, parent, N):
		nodes = [None] * N
		root = None
		for i in range(N):
			if nodes[i] is None:
				cnode = Node(i)
				nodes[i] = cnode
			cnode = nodes[i]
			j = parent[i]
			if j == -1:
				if root is None:
					root = cnode
			else:
				if nodes[j] is None:
					pnode = Node(j)
					nodes[j] = pnode
					if parent[j] == -1 and root is None:
						root = pnode
				else:
					pnode = nodes[j]
				if pnode.left is None:
					pnode.left = cnode
				elif pnode.right is None:
					pnode.right = cnode
		return root


class Solution:

	def createTree(self, parent, N):
		hashmap = {}
		nodemap = {}
		nodemap[-1] = Node(-1)
		for i in range(0, N):
			if i in nodemap:
				continue
			else:
				nodemap[i] = Node(i)
		for i in range(0, N):
			if nodemap[parent[i]] in hashmap:
				hashmap[nodemap[parent[i]]].append(nodemap[i])
			else:
				hashmap[nodemap[parent[i]]] = [nodemap[i]]
		for keys in hashmap:
			ParentNode = keys
			if ParentNode.key == -1:
				continue
			if len(hashmap[keys]) == 1:
				ParentNode.left = hashmap[keys][0]
			else:
				ParentNode.left = hashmap[keys][0]
				ParentNode.right = hashmap[keys][1]
		return hashmap[nodemap[-1]][0]


class Node:

	def __init__(self, key):
		self.key = key
		self.left = None
		self.right = None
from collections import defaultdict, deque

class Solution:

	def createTree(self, parent, N):
		d = defaultdict(list)
		for (i, par) in enumerate(parent):
			d[par].append(i)
		node = Node(d[-1][0])
		q = deque([node])
		head = q[0]
		while q:
			node = q.popleft()
			data = node.key
			if data in d:
				node.left = Node(d[data][0])
				q.append(node.left)
				if len(d[data]) == 2:
					node.right = Node(d[data][1])
					q.append(node.right)
		return head


from collections import defaultdict

class Solution:

	def createTree(self, parent, N):

		def construct_edges():
			connectivity = defaultdict(list)
			for (node_val, parent_val) in enumerate(parent):
				connectivity[parent_val].append(node_val)
			return connectivity

		def construct_tree(val_node):
			node = Node(val_node)
			childs = connectivity[val_node]
			if not childs:
				return node
			left = childs[0]
			right = childs[-1]
			node.left = construct_tree(left)
			if right != left:
				node.right = construct_tree(right)
			return node
		connectivity = construct_edges()
		root_val = connectivity[-1][0]
		tree = construct_tree(root_val)
		return tree


class treenode:

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

class Solution:

	def constree(self, root, hashmap):
		if root.key in hashmap:
			if len(hashmap[root.key]) == 1:
				root.left = treenode(hashmap[root.key][0])
				self.constree(root.left, hashmap)
			else:
				root.left = treenode(hashmap[root.key][0])
				root.right = treenode(hashmap[root.key][1])
				self.constree(root.left, hashmap)
				self.constree(root.right, hashmap)

	def createTree(self, parent, N):
		hashmap = {}
		idx = 0
		for values in parent:
			if values not in hashmap:
				hashmap[values] = [idx]
			else:
				hashmap[values].append(idx)
			idx += 1
		root = treenode(hashmap[-1][0])
		self.constree(root, hashmap)
		return root


class Solution:

	def createTree(self, parents, N):
		m = {}
		root = None
		for i in range(N):
			node = Node(i)
			m[i] = node
			if parents[i] == -1:
				root = node
		for i in range(N):
			if parents[i] == -1:
				continue
			parent = m.get(parents[i])
			child = m.get(i)
			if parent.left is None:
				parent.left = child
			else:
				parent.right = child
		return root


class Solution:

	def createTree(self, parent, N):
		Map = {}
		root = None
		for i in range(N):
			Map[i] = Node(i)
		for i in range(N):
			val = parent[i]
			if val == -1:
				root = Map[i]
			else:
				node = Map[i]
				p = Map[val]
				if p.left:
					p.right = node
				else:
					p.left = node
		return root


class Solution:

	def createTree(self, parent, N):
		dic = {}
		for i in range(N):
			node = Node(i)
			if parent[i] == -1:
				root = node
			dic[i] = node
		for i in range(N):
			if parent[i] == -1:
				continue
			c = dic[i]
			p = dic[parent[i]]
			if not p.left:
				p.left = c
			else:
				p.right = c
		return root


class Solution:

	def createNode(self, parent, i, created, root):
		if created[i]:
			return
		created[i] = Node(i)
		if parent[i] == -1:
			root[0] = created[i]
			return
		if created[parent[i]] is None:
			self.createNode(parent, parent[i], created, root)
		p = created[parent[i]]
		if p.left is None:
			p.left = created[i]
		else:
			p.right = created[i]

	def createTree(self, parent, N):
		created = [None for _ in range(N)]
		root = [None]
		for i in range(N):
			self.createNode(parent, i, created, root)
		return root[0]


class Solution:

	def createTree(self, parent, N):
		dic = {}
		for i in range(N):
			if parent[i] == -1:
				root = Node(i)
				dic[i] = root
			if parent[i] != -1:
				dic[i] = Node(i)
		for i in range(N):
			if parent[i] != -1:
				new = dic.get(parent[i])
				if new.left == None:
					new.left = dic[i]
				else:
					new.right = dic[i]
		return root


class Solution:

	def createTree(self, parent, n):
		hashMap = {}
		root = None
		for i in range(n):
			hashMap[i] = Node(i)
		for i in range(n):
			if parent[i] == -1:
				root = hashMap[i]
			elif hashMap[parent[i]].left == None:
				hashMap[parent[i]].left = hashMap[i]
			else:
				hashMap[parent[i]].right = hashMap[i]
		return root


from collections import Counter

class Solution:

	def createTree(self, parent, N):
		d = {}
		for i in range(len(parent)):
			d[i] = Node(i)
		root = None
		for (i, e) in enumerate(parent):
			if e == -1:
				root = d[i]
			else:
				ptr = d[e]
				if ptr.left:
					ptr.right = d[i]
				else:
					ptr.left = d[i]
		return root


class Solution:

	def createTree(self, parent, N):
		tree = list(map(Node, range(n)))
		root = None
		for i in range(n):
			if parent[i] == -1:
				root = tree[i]
			elif not tree[parent[i]].left:
				tree[parent[i]].left = tree[i]
			else:
				tree[parent[i]].right = tree[i]
		return root


from collections import deque

class Node:

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

class Solution:

	def createTree(self, parent, N):
		parent_hm = {}
		for i in range(N):
			if parent[i] not in parent_hm:
				parent_hm[parent[i]] = []
			parent_hm[parent[i]].append(i)
		queue = deque()
		root = Node(parent_hm[-1][0])
		queue.append(root)
		while len(queue):
			k = len(queue)
			while k:
				k -= 1
				tmp = queue.popleft()
				val = tmp.key
				if val in parent_hm:
					node1 = Node(parent_hm[val][0])
					tmp.left = node1
					queue.append(node1)
					if len(parent_hm[val]) == 2:
						node2 = Node(parent_hm[val][1])
						tmp.right = node2
						queue.append(node2)
		return root


class Solution:

	def createTree(self, arr, n):
		self.mp = {}
		for i in range(n):
			val = arr[i]
			if val in self.mp:
				self.mp[val].append(i)
			else:
				self.mp[val] = [i]
		root_idx = self.mp[-1]
		return self.func(arr, root_idx[0])

	def func(self, arr, node_val):
		if node_val in self.mp:
			root = Node(node_val)
			child_idx_arr = self.mp[node_val]
			root.left = self.func(arr, child_idx_arr[0])
			if len(child_idx_arr) == 2:
				root.right = self.func(arr, child_idx_arr[1])
			return root
		else:
			return Node(node_val)


class Solution:

	def createTree(self, parent, N):
		root = None
		node_arr = [None for i in range(N)]
		for i in range(N):
			if not node_arr[i]:
				node_arr[i] = Node(i)
			if not node_arr[parent[i]] and parent[i] != -1:
				node_arr[parent[i]] = Node(parent[i])
			child = node_arr[i]
			parent_ = node_arr[parent[i]]
			if parent[i] == -1:
				root = child
			elif not (parent_.left or parent_.right):
				parent_.left = child
			else:
				parent_.right = child
		return root


from collections import defaultdict

class Solution:

	def createTree(self, parent, N):
		(node_map, root) = (defaultdict(list), None)
		for (i, val) in enumerate(parent):
			node_map[val].append(i)
			if val == -1:
				root = Node(i)

		def build(root):
			if not root:
				return None
			children = node_map[root.key]
			if children:
				root.left = Node(children[0])
			if len(children) > 1:
				root.right = Node(children[1])
			build(root.left)
			build(root.right)
			return root
		return build(root)


from collections import deque

class Solution:

	def createTree(self, parent, N):
		dic = dict()
		for i in range(N):
			if parent[i] not in dic:
				dic[parent[i]] = []
			dic[parent[i]].append(i)
		root = Node(dic[-1][0])
		q = deque()
		q.append(root)
		while q:
			nod = q.popleft()
			if nod.key in dic:
				nod.left = Node(dic[nod.key][0])
				q.append(nod.left)
				if len(dic[nod.key]) > 1:
					nod.right = Node(dic[nod.key][1])
					q.append(nod.right)
		return root


class Solution:

	def createTree(self, parent, N):
		alle = {}
		for (p, key) in enumerate(parent):
			if p not in alle:
				alle[p] = Node(p)
			if key not in alle:
				if key == -1:
					root = alle[p]
				else:
					alle[key] = Node(key)
			if key != -1:
				if not alle[key].left:
					alle[key].left = alle[p]
				else:
					alle[key].right = alle[p]
		return root


class Solution:

	def createTree(self, par, N):
		m = {}
		for i in range(N):
			new = Node(i)
			m[i] = new
		for i in range(N):
			if par[i] == -1:
				root = m[i]
			elif m[par[i]].left == None:
				m[par[i]].left = m[i]
			else:
				m[par[i]].right = m[i]
		return root


class Solution:

	def createTree(self, parent, N):

		def build(root, d):
			if root == None:
				return None
			if root.key not in d:
				return root
			for i in d[root.key]:
				if root.left == None:
					root.left = Node(i)
				else:
					root.right = Node(i)
			build(root.left, d)
			build(root.right, d)
			return root
		d = {}
		for i in range(len(parent)):
			if parent[i] not in d:
				d[parent[i]] = []
			d[parent[i]].append(i)
		root = Node(d[-1][0])
		z = build(root, d)
		return z


class Solution:

	def createTree(self, parent, N):
		arr = [None for i in range(N)]
		root = [None]

		def func(i):
			if arr[i]:
				return
			arr[i] = Node(i)
			if parent[i] == -1:
				root[0] = arr[i]
				return
			if not arr[parent[i]]:
				func(parent[i])
			p = arr[parent[i]]
			if not p.left:
				p.left = arr[i]
			else:
				p.right = arr[i]
			return
		for i in range(N):
			func(i)
		return root[0]


class Solution:

	def createTree(self, parent, N):
		ans = [None] * N
		neg_parent = Node(parent.index(-1))
		ans[parent.index(-1)] = neg_parent
		for i in range(N):
			if parent[i] == -1:
				continue
			if ans[parent[i]] == None:
				nod = Node(parent[i])
				ans[parent[i]] = nod
			if ans[i] == None:
				nod = Node(i)
				ans[i] = nod
			if ans[parent[i]].left == None:
				ans[parent[i]].left = ans[i]
			else:
				ans[parent[i]].right = ans[i]
		return ans[parent.index(-1)]


class Solution:

	def createTree(self, p, n):
		d = {}
		for i in range(len(p)):
			if p[i] == -1:
				rot = i
			elif p[i] not in d:
				d[p[i]] = [i]
			else:
				d[p[i]].append(i)
		root = Node(rot)

		def rt(root, d):
			if root.key in d:
				if len(d[root.key]) == 1:
					root.left = Node(d[root.key][0])
				else:
					root.left = Node(d[root.key][0])
					root.right = Node(d[root.key][1])
			if root.left:
				rt(root.left, d)
			if root.right:
				rt(root.right, d)
		rt(root, d)
		return root


class Node:

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

class Solution:

	def createTree(self, parent, N):
		arr = [Node(i) for i in range(N)]
		for (i, x) in enumerate(parent):
			if x == -1:
				res = i
			elif arr[x].left:
				arr[x].right = arr[i]
			else:
				arr[x].left = arr[i]
		return arr[res]


class Solution:

	def __init__(self):
		self.root = None

	def createTree(self, parent, N):
		mp = {}
		s = set()
		for i in range(N):
			mp[i] = Node(i)
		for i in range(N):
			if parent[i] == -1:
				self.root = mp[i]
			elif parent[i] in s:
				mp[parent[i]].right = mp[i]
			else:
				mp[parent[i]].left = mp[i]
				s.add(parent[i])
		return self.root


class Solution:

	def createTree(self, parent, N):
		d = dict()
		root = [None]

		def createNodes(val, p):
			if i not in d:
				d[i] = Node(i)
			if p == -1:
				root[0] = d[i]
			else:
				if p not in d:
					d[p] = Node(p)
				parent = d[p]
				if parent.left:
					parent.right = d[i]
				else:
					parent.left = d[i]
		for i in range(N):
			createNodes(i, parent[i])
		return root[0]


class Solution:

	def createTree(self, parent, N):
		dics = {}
		for i in range(len(parent)):
			dics[i] = Node(i)
		for (ind, val) in enumerate(parent):
			if val == -1:
				root = dics[ind]
			else:
				node = dics[val]
				if node.left:
					node.right = dics[ind]
				else:
					node.left = dics[ind]
		return root


class Solution:

	def createTree(self, p, N):
		l = []
		for i in range(N):
			l.append(Node(i))
		for i in range(N):
			if p[i] != -1:
				if l[p[i]].left is None:
					l[p[i]].left = l[i]
				else:
					l[p[i]].right = l[i]
			else:
				g = i
		return l[g]


class Solution:

	def createTree(self, parent, N):
		mp = {}
		for (i, p) in enumerate(parent):
			if i not in mp:
				mp[i] = Node(i)
			if p == -1:
				root = mp[i]
			elif p in mp:
				if not mp[p].left:
					mp[p].left = mp[i]
				else:
					mp[p].right = mp[i]
			else:
				mp[p] = Node(p)
				if not mp[p].left:
					mp[p].left = mp[i]
				else:
					mp[p].right = mp[i]
		return root


class Solution:

	def createTree(self, parent, N):
		hash_map = {}
		for i in range(N):
			hash_map.setdefault(i, Node(i))
		for (idx, p) in enumerate(parent):
			if p == -1:
				root = hash_map[idx]
			elif hash_map[p].left:
				hash_map[p].right = hash_map[idx]
			else:
				hash_map[p].left = hash_map[idx]
		return root


class Solution:

	def createTree(self, parent, N):
		arr = [Node(i) for i in range(len(parent))]
		d = {}
		ind = 0
		for i in range(len(parent)):
			if parent[i] != -1:
				if parent[i] in d:
					arr[parent[i]].right = arr[i]
				else:
					arr[parent[i]].left = arr[i]
					d[parent[i]] = 1
			else:
				ind = i
		return arr[ind]


class Solution:

	def createTree(self, parent, N):
		valNodeMap = {}
		for i in range(N):
			valNodeMap[i] = Node(i)
		root = Node(0)
		for i in range(len(parent)):
			if parent[i] == -1:
				root = valNodeMap[i]
			elif valNodeMap[parent[i]].left is None:
				valNodeMap[parent[i]].left = valNodeMap[i]
			else:
				valNodeMap[parent[i]].right = valNodeMap[i]
		return root


class Solution:

	def createTree(self, parent, N):
		d = {}
		for i in range(len(parent)):
			if parent[i] in d.keys():
				d[parent[i]].append(i)
			else:
				d[parent[i]] = [i]

		def f(root, x):
			node = Node(x)
			if x in d.keys() and len(d[x]) > 0:
				node.left = f(node.left, d[x].pop(0))
			if x in d.keys() and len(d[x]) > 0:
				node.right = f(node.right, d[x].pop(0))
			return node
		return f(None, d[-1][0])


class Solution:

	def createTree(self, parent, N):
		if N == 0:
			return
		hash = {}
		for i in range(N):
			hash[i] = Node(i)
		for i in range(N):
			if parent[i] == -1:
				head = hash[i]
			elif hash[parent[i]].left == None:
				hash[parent[i]].left = hash[i]
			else:
				hash[parent[i]].right = hash[i]
		return head


class Solution:

	def createTree(self, parents, N):
		node_address_map = {}
		for i in range(N):
			node_address_map[i] = Node(i)
		root = None
		for i in range(N):
			child = i
			parent = parents[i]
			if parent == -1:
				root = node_address_map[child]
			elif node_address_map[parent].left is None:
				node_address_map[parent].left = node_address_map[child]
			else:
				node_address_map[parent].right = node_address_map[child]
		return root


from collections import defaultdict

class Solution:

	def createTree(self, parent, N):
		child = defaultdict(list)
		noderep = defaultdict(int)
		for i in range(N):
			child[parent[i]].append(i)
		root = Node(child[-1][0])
		noderep[child[-1][0]] = root
		for i in range(N):
			n = len(child[i])
			if i not in noderep:
				node = Node(i)
				noderep[i] = node
			node = noderep[i]
			if n >= 1:
				if child[i][0] not in noderep:
					child1 = Node(child[i][0])
					noderep[child[i][0]] = child1
				child1 = noderep[child[i][0]]
				node.left = child1
			if n == 2:
				if child[i][1] not in noderep:
					child2 = Node(child[i][1])
					noderep[child[i][1]] = child2
				child2 = noderep[child[i][1]]
				node.right = child2
		return root