Given two arrays that represent Preorder traversals of a Full binary tree preOrder[] and its mirror tree preOrderMirror[], your task is to complete the function constructBinaryTree(), that constructs the full binary tree using these two Preorder traversals.
Note: It is not possible to construct a general binary tree using these two traversal. But it is possible to create a full binary tree using the above traversals without any ambiguity.
Example 1:
Input :
preOrder[] = {0,1,2}
preOrderMirror[] = {0,2,1} 
Output :
                0
              /   \
             1     2
Explanation :
Tree in the output and it's mirror tree matches the preOrder and preOrderMirror.
Example 2:
Input :  
preOrder[] = {1,2,4,5,3,6,7}
preOrderMirror[] = {1,3,7,6,2,5,4}
Output :          
                 1
               /    \
              2      3
            /   \   /  \
           4     5 6    7
Explanation :
Tree in the output and it's mirror tree matches the preOrder and preOrderMirror.
Your Task:
You don't need to read, input, or print anything. Your task is to complete the function constructBTree, The function takes three arguments as input, first the array that represent Preorder traversals of a Full binary tree preOrder[], second the array that represents the preorder traversal of its mirror tree preOrderMirror[] and last the size of both the array,and returns root of the full binary tree.
Expected Time Complexity: O(N^2)
Expected Auxiliary Space: O(N), where N indicates number of nodes.
Constraints:
1 <= Number of Nodes <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3


# your task is to complete this function
# function should create a new binary tree
# function should return the root node to the 
# new binary tree formed
class Solution:
    def constructBinaryTree(self, pre, preMirror, size):
        # code here

Solutions:
class Node:

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

class Solution:

	def constructBinaryTree(self, pre, preM, n):
		self.i = 0
		return self.util(pre, preM, n)

	def util(self, pre, preM, n):
		if self.i == n:
			return None
		j = 0
		while j < n:
			if preM[j] == pre[self.i]:
				break
			j += 1
		preM[j] = -1
		root = Node(pre[self.i])
		self.i += 1
		if j == n - 1 or preM[j + 1] == -1:
			return root
		root.left = self.util(pre, preM, n)
		root.right = self.util(pre, preM, n)
		return root


class TreeNode:

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

class Solution:

	def solve(self, prei, prem, pre, preM, size, dM, dPre):
		if prei >= size or prem >= size:
			return None
		r = TreeNode(pre[prei])
		if prei < size - 1:
			left = pre[prei + 1]
			leftM = dM[left]
			if leftM > dM[pre[prei]]:
				r.left = self.solve(prei + 1, leftM, pre, preM, size, dM, dPre)
				if prem + 1 < size:
					right = preM[prem + 1]
					rightI = dPre[right]
					r.right = self.solve(rightI, prem + 1, pre, preM, size, dM, dPre)
		return r

	def constructBinaryTree(self, pre, preMirror, size):
		try:
			d = {}
			for i in range(size):
				d[preMirror[i]] = i
			d1 = {}
			for i in range(size):
				d1[pre[i]] = i
			return self.solve(0, 0, pre, preMirror, size, d, d1)
		except Exception as e:
			print(e)


class Node:

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

class Solution:

	def constructBinaryTree(self, pre, preMirror, size):
		(i, j) = (0, len(pre) - 1)

		def construct():
			nonlocal i, j
			if pre[i] == preMirror[j]:
				root = Node(pre[i])
				i += 1
				j -= 1
				return root
			else:
				root = Node(pre[i])
				i += 1
				root.left = construct()
				root.right = construct()
				j -= 1
				return root
		return construct()


class Node:

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

class Solution:

	def run(self, pre, l, r):
		if l > r:
			return None
		tmp = Node(pre[l])
		if l != r:
			mid = l + (r - l) // 2
			tmp.left = self.run(pre, l + 1, mid)
			tmp.right = self.run(pre, mid + 1, r)
		return tmp

	def constructBinaryTree(self, pre, preMirror, size):
		return self.run(pre, 0, size - 1)


class Node:

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

class Solution:

	def helper(self, pre, l, r):
		mid = (l + r) // 2
		node = Node(pre[l])
		if l < r:
			node.left = self.helper(pre, l + 1, mid)
			node.right = self.helper(pre, mid + 1, r)
		return node

	def constructBinaryTree(self, pre, preMirror, size):
		root = self.helper(pre, 0, size - 1)
		return root


class newNode:

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

class Solution:

	def constructBinaryTree(self, pre, preMirror, size):

		def constructBinaryTreeUtil(pre, preM, preIndex, l, h, size):
			if preIndex >= size or l > h:
				return (None, preIndex)
			root = newNode(pre[preIndex])
			preIndex += 1
			if l == h:
				return (root, preIndex)
			i = 0
			for i in range(l, h + 1):
				if pre[preIndex] == preM[i]:
					break
			if i <= h:
				(root.left, preIndex) = constructBinaryTreeUtil(pre, preM, preIndex, i, h, size)
				(root.right, preIndex) = constructBinaryTreeUtil(pre, preM, preIndex, l + 1, i - 1, size)
			return (root, preIndex)
		preIndex = 0
		preMIndex = 0
		(root, x) = constructBinaryTreeUtil(pre, preMirror, preIndex, 0, size - 1, size)
		return root


class Node:

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

class Solution:

	def solve(self, pre, preMirror, l1, r1, l2, r2):
		if l1 > r1:
			return None
		if l1 == r1:
			return Node(pre[l1])
		p = Node(pre[l1])
		idx = preMirror.index(pre[l1 + 1])
		if idx == l2 + 1:
			p.left = self.solve(pre, preMirror, l1 + 1, r1, l2 + 1, r2)
		else:
			right_idx = pre.index(preMirror[l2 + 1])
			p.left = self.solve(pre, preMirror, l1 + 1, right_idx - 1, idx, r2)
			p.right = self.solve(pre, preMirror, right_idx, r1, l2 + 1, idx - 1)
		return p

	def constructBinaryTree(self, pre, preMirror, size):
		return self.solve(pre, preMirror, 0, size - 1, 0, size - 1)


class Node:

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

class Solution:

	def constructBinaryTree(self, pre, preMirror, size):
		(i, j) = ([0], [len(pre) - 1])

		def construct():
			if j[0] < 0 or i[0] >= len(pre):
				return None
			if pre[i[0]] == preMirror[j[0]]:
				root = Node(pre[i[0]])
				i[0] += 1
				j[0] -= 1
				return root
			else:
				root = Node(pre[i[0]])
				i[0] += 1
				root.left = construct()
				root.right = construct()
				j[0] -= 1
				return root
		try:
			return construct()
		except Exception as e:
			print(e)
			return None