Given Preorder, Inorder and Postorder traversals of some tree of size N. The task is to check if they are all of the same tree or not.
Example 1:
Input:
N = 5
preorder[] = {1, 2, 4, 5, 3}
inorder[] = {4, 2, 5, 1, 3}
postorder[] = {4, 5, 2, 3, 1}
Output: Yes
Explanation: 
All of the above three traversals 
are of the same tree.
           1
         /   \
        2     3
      /   \
     4     5
Example 2:
Input:
N = 5
preorder[] = {1, 5, 4, 2, 3}
inorder[] = {4, 2, 5, 1, 3}
postorder[] = {4, 1, 2, 3, 5}
Output: No
Explanation: The three traversals can 
not be of the same tree.
Your Task:
You don't need to read input or print anything. Complete the function checktree() which takes the array preorder[ ], inorder[ ], postorder[ ] and integer N as input parameters and returns true if the three traversals are of the same tree or not. 
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}
Node values are unique.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:
    def checktree(self, preorder, inorder, postorder, N): 
        # Your code goes here


Solutions:
class Solution:

	def check(self, pre, l1, r1, ino, l2, r2, post, l3, r3):
		if l2 > r2:
			return True
		if pre[l1] != post[r3]:
			return False
		try:
			idx = ino.index(pre[l1])
		except ValueError:
			return False
		return self.check(pre, l1 + 1, idx - l2 + l1, ino, l2, idx - 1, post, l3, l3 + idx - l2 - 1) and self.check(pre, r1 + 1 - r2 + idx, r1, ino, idx + 1, r2, post, r3 + idx - r2, r3 - 1)

	def checktree(self, preorder, inorder, postorder, N):
		return self.check(preorder, 0, N - 1, inorder, 0, N - 1, postorder, 0, N - 1)


class Node:

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

class Solution:

	def Search(self, start, end, inorder, val):
		for i in range(start, end + 1):
			if inorder[i] == val:
				return i
		return -1

	def ConstructTree(self, start, end, preindx, N, preorder, inorder, ans):
		if start > end:
			return None
		if preindx[0] >= N:
			return None
		root = Node(preorder[preindx[0]])
		indx = self.Search(start, end, inorder, preorder[preindx[0]])
		if indx == -1:
			ans[0] = False
		preindx[0] += 1
		root.left = self.ConstructTree(start, indx - 1, preindx, N, preorder, inorder, ans)
		root.right = self.ConstructTree(indx + 1, end, preindx, N, preorder, inorder, ans)
		return root

	def Postorder(self, root, postindx, N, postorder, ans):
		if root == None:
			return
		if postindx[0] >= N:
			return
		self.Postorder(root.left, postindx, N, postorder, ans)
		self.Postorder(root.right, postindx, N, postorder, ans)
		if root.data != postorder[postindx[0]]:
			ans[0] = False
		postindx[0] += 1

	def checktree(self, preorder, inorder, postorder, N):
		preindx = [0]
		ans = [True]
		root = self.ConstructTree(0, N - 1, preindx, N, preorder, inorder, ans)
		if ans[0] == False:
			return False
		postindx = [0]
		self.Postorder(root, postindx, N, postorder, ans)
		return ans[0]


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return True
		if N == 1:
			return preorder[0] == postorder[0] and postorder[0] == inorder[0]
		root = preorder[0]
		if root != postorder[N - 1]:
			return False
		if root not in set(inorder):
			return False
		else:
			rooti = inorder.index(root)
			leftN = rooti
			rightN = N - rooti - 1
			return self.checktree(preorder[1:leftN + 1], inorder[:rooti], postorder[:leftN], leftN) and self.checktree(preorder[leftN + 1:], inorder[rooti + 1:], postorder[leftN:N - 1], rightN)


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return True
		if N == 1:
			return inorder[0] == preorder[0] and preorder[0] == postorder[0]
		root = preorder[0]
		if root != postorder[N - 1]:
			return False
		if root not in set(inorder):
			return False
		else:
			for i in range(N):
				if inorder[i] == postorder[N - 1]:
					break
		return self.checktree(preorder[1:i + 1], inorder[:i], postorder[:i], i) and self.checktree(preorder[i + 1:], inorder[i + 1:], postorder[i:N - 1], N - i - 1)


class Node:

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

class Solution:

	def checktree(self, preorder, inorder, postorde, N):

		def postorder(root):
			if root is None:
				return []
			return postorder(root.left) + postorder(root.right) + [root.data]

		def recursive(inorder, preorder, N, idx=0, left=0, right=N - 1):
			if idx == N:
				return (None, idx)
			cur = preorder[idx]
			root = None
			for i in range(left, right + 1):
				if inorder[i] == cur:
					root = Node(cur)
					break
			if root:
				(root.left, idx) = recursive(inorder, preorder, N, idx + 1, left, i - 1)
				(root.right, idx) = recursive(inorder, preorder, N, idx, i + 1, right)
			return (root, idx)
		(root, idx) = recursive(inorder, preorder, N)
		post = postorder(root)
		if post == postorde:
			return True
		else:
			return False


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return True
		if N == 1:
			return preorder[0] == postorder[0] and postorder[0] == inorder[0]
		root = preorder[0]
		if root != postorder[N - 1]:
			return False
		if root not in set(inorder):
			return False
		else:
			index = inorder.index(root)
			left = index
			right = N - index - 1
			return self.checktree(preorder[1:left + 1], inorder[:index], postorder[:left], left) and self.checktree(preorder[left + 1:], inorder[index + 1:], postorder[left:N - 1], right)


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return True
		if N == 1:
			return preorder[0] == postorder[0] and postorder[0] == inorder[0]
		root = preorder[0]
		if root != postorder[-1]:
			return False
		if root not in set(inorder):
			return False
		else:
			index = inorder.index(root)
			lst = index
			rst = N - index - 1
			return self.checktree(preorder[1:index + 1], inorder[:index], postorder[:lst], lst) and self.checktree(preorder[lst + 1:], inorder[index + 1:], postorder[lst:N - 1], rst)


class Node:

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

class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		m = {}
		for i in range(N):
			m[inorder[i]] = i
		l = [0]

		def construct(st, end):
			if st > end:
				return None
			node = Node(preorder[l[0]])
			pos = m[preorder[l[0]]]
			l[0] += 1
			try:
				node.left = construct(st, pos - 1)
				node.right = construct(pos + 1, end)
			except:
				return None
			return node
		root = construct(0, N - 1)
		l = []

		def post(r):
			if r:
				post(r.left)
				post(r.right)
				l.append(r.data)
		post(root)
		return l == postorder


class Node:

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

class Solution:

	def build(self, pre, ino):
		tem = [True]
		n = len(pre)

		def rec(st, en, n):
			if st > en or ind[0] >= n or tem[0] == None:
				return
			nod = Node(pre[ind[0]])
			ind[0] += 1
			idx = st - 1
			for i in range(st, en + 1):
				if ino[i] == nod.val:
					idx = i
					break
			if idx == st - 1:
				tem[0] = None
				return
			nod.left = rec(st, idx - 1, n)
			nod.right = rec(idx + 1, en, n)
			return nod
		ind = [0]
		root = Node(pre[0])
		ind[0] += 1
		idx = inorder.index(root.val)
		root.left = rec(0, idx - 1, n)
		root.right = rec(idx + 1, n - 1, n)
		if tem[0] == None:
			return tem[0]
		return root

	def checktree(self, preorder, inorder, postorder, N):
		root = self.build(preorder, inorder)
		if root is None:
			return False
		ind = [0, True]

		def rec(nod, n):
			if nod is None or ind[1] == False:
				return
			if nod is not None and ind[0] >= n:
				ind[1] = False
				return
			rec(nod.left, n)
			rec(nod.right, n)
			if postorder[ind[0]] != nod.val:
				ind[1] = False
				return
			ind[0] += 1
		rec(root, N)
		return ind[1]


class Solution:

	def checktree(self, preorder, inorder, postorder, N):

		def f(inord, pre, st, en, i, n, d, arr):
			if st > en or i[0] >= n:
				return
			pos = d[pre[i[0]]]
			val = pre[i[0]]
			i[0] += 1
			f(inord, pre, st, pos - 1, i, n, d, arr)
			f(inord, pre, pos + 1, en, i, n, d, arr)
			arr += [val]
		ind = [0]
		d = {}
		for i in range(N):
			d[inorder[i]] = i
		arr = []
		f(inorder, preorder, 0, N - 1, ind, N, d, arr)
		for i in range(N):
			if arr[i] != postorder[i]:
				return False
		return True


class Solution:

	def checktreeutil(self, preorder, inorder, postorder):
		if len(preorder) >= 1 and len(postorder) >= 1 and (len(inorder) >= 1):
			if len(preorder) != len(postorder):
				return False
			temp = -10000000
			for i in range(len(inorder)):
				if inorder[i] == preorder[0]:
					temp = i
			if temp == -10000000:
				return False
			if len(preorder) != 0 and len(postorder) != 0:
				if preorder[0] != postorder[len(postorder) - 1]:
					return False
			return self.checktreeutil(preorder[1:1 + temp], inorder[0:temp], postorder[0:temp]) and self.checktreeutil(preorder[temp + 1:], inorder[temp + 1:], postorder[temp:len(postorder) - 1])
		return True

	def checktree(self, preorder, inorder, postorder, N):
		return self.checktreeutil(preorder, inorder, postorder)


class node:

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

class Solution:

	def checktree(self, pr, io, po, n):
		valid = True

		def f(pr, io):
			nonlocal valid
			if not valid:
				return
			if len(pr) == 0 and len(io) == 0:
				return
			if len(pr) != len(io) or pr[0] not in io:
				valid = False
				return
			if len(pr) == 1:
				z.append(pr[0])
				return
			i = io.index(pr[0])
			if len(pr) > 1:
				f(pr[1:i + 1], io[:i])
			f(pr[i + 1:], io[i + 1:])
			z.append(pr[0])
		z = []
		f(pr, io)
		return z == po


class Node:

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

class Solution:

	def checktree(self, preorder, inorder, postorder, N):

		def postOrder(root):
			if root:
				postOrder(root.left)
				postOrder(root.right)
				post.append(root.data)

		def buildTree(inStart, inEnd, preStart, preEnd):
			if inStart > inEnd or preStart > preEnd:
				return None
			root = Node(preorder[preStart])
			inRoot = inMap[root.data]
			inLeft = inRoot - inStart
			root.left = buildTree(inStart, inRoot - 1, preStart + 1, preStart + inLeft)
			root.right = buildTree(inRoot + 1, inEnd, preStart + inLeft + 1, preEnd)
			return root
		inMap = {}
		for i in range(N):
			inMap[inorder[i]] = i
		try:
			root = buildTree(0, N - 1, 0, N - 1)
		except:
			return False
		post = []
		postOrder(root)
		for i in range(N):
			if postorder[i] != post[i]:
				return False
		return True


class Node:

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

class Solution:

	def post(self, root, crr):
		if root == None:
			return
		self.post(root.left, crr)
		self.post(root.right, crr)
		crr.append(root.data)
		return crr

	def solve(self, pre, ino, N, arr, s, e, hm):
		if arr[0] >= N or s > e:
			return None
		el = pre[arr[0]]
		root = Node(el)
		arr[0] += 1
		pos = hm[el] - 1
		root.left = self.solve(pre, ino, N, arr, s, pos - 1, hm)
		root.right = self.solve(pre, ino, N, arr, pos + 1, e, hm)
		return root

	def checktree(self, preorder, inorder, postorder, N):
		hm = {}
		for i in range(N):
			hm[inorder[i]] = i + 1
		arr = [0]
		s = 0
		e = N - 1
		root = self.solve(preorder, inorder, N, arr, s, e, hm)
		crr = []
		crr = self.post(root, crr)
		if crr == postorder:
			return 1
		return 0


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return True
		if N == 1:
			return preorder[0] == postorder[0] and postorder[0] == inorder[0]
		root = preorder[0]
		idx = -1
		for i in range(N):
			if inorder[i] == preorder[0]:
				idx = i
				break
		if idx == -1:
			return False
		if preorder[0] != postorder[N - 1]:
			return False
		w1 = self.checktree(preorder[1:], inorder, postorder, idx)
		w2 = self.checktree(preorder[idx + 1:], inorder[idx + 1:], postorder[idx:], N - idx - 1)
		return w1 and w2


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if not preorder and (not inorder) and (not postorder):
			return True
		if len(preorder) != len(inorder) or len(inorder) != len(postorder) or len(postorder) != len(preorder):
			return False
		preorderRoot = preorder[0]
		postorderRoot = postorder[-1]
		if preorderRoot != postorderRoot:
			return False
		try:
			rootIndex = inorder.index(preorderRoot)
		except ValueError:
			return False
		leftsubTree = self.checktree(preorder[1:rootIndex + 1], inorder[:rootIndex], postorder[:rootIndex], N)
		rightsubTree = self.checktree(preorder[rootIndex + 1:], inorder[rootIndex + 1:], postorder[rootIndex:-1], N)
		return leftsubTree and rightsubTree


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return True
		if preorder[0] != postorder[-1]:
			return False
		root = preorder[0]
		if root not in inorder:
			return False
		else:
			p = inorder.index(preorder[0])
			lt = self.checktree(preorder[1:p + 1], inorder[:p], postorder[:p], p)
			rt = self.checktree(preorder[p + 1:], inorder[p + 1:], postorder[p:N - 1], N - p - 1)
			return lt & rt


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return 1
		if N == 1:
			return preorder[0] == inorder[0] and inorder[0] == postorder[0]
		idx = -1
		for i in range(N):
			if inorder[i] == preorder[0]:
				idx = i
				break
		if idx == -1:
			return 0
		if preorder[0] != postorder[N - 1]:
			return 0
		ret1 = self.checktree(preorder[1:], inorder, postorder, idx)
		ret2 = self.checktree(preorder[idx + 1:], inorder[idx + 1:], postorder[idx:], N - idx - 1)
		return ret1 and ret2


class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		if N == 0:
			return True
		if N == 1:
			return preorder[0] == inorder[0] and inorder[0] == postorder[0]
		root = preorder[0]
		if root != postorder[N - 1]:
			return False
		if root not in set(inorder):
			return False
		else:
			index_of_root = inorder.index(root)
			left_part = index_of_root
			right_part = N - index_of_root - 1
			return self.checktree(preorder[1:left_part + 1], inorder[:index_of_root], postorder[:left_part], left_part) and self.checktree(preorder[left_part + 1:], inorder[index_of_root + 1:], postorder[left_part:N - 1], right_part)


class Solution:

	def checktree(self, preorder, inorder, postorder, n):
		if not n:
			return True
		if n == 1:
			return preorder[0] == postorder[0] and postorder[0] == inorder[0]
		idx = -1
		for i in range(n):
			if inorder[i] == preorder[0]:
				idx = i
				break
		if idx == -1:
			return 0
		if preorder[0] != postorder[n - 1]:
			return 0
		left = self.checktree(preorder[1:], inorder, postorder, idx)
		right = self.checktree(preorder[idx + 1:], inorder[idx + 1:], postorder[idx:], n - idx - 1)
		return left and right


class Node:

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

class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		inorder_map = {inorder[i]: i for i in range(len(inorder))}
		ind = [0]
		root = build(preorder, ind, 0, len(inorder) - 1, inorder_map)
		res = [True]
		ind = [0]
		check_same(root, postorder, ind, res)
		traverse_to_end = ind[0] == len(postorder)
		return res[0] and traverse_to_end

def build(preorder, ind, inorder_l, inorder_h, inorder_map):
	if ind[0] == len(preorder):
		return None
	val = preorder[ind[0]]
	inorder_i = inorder_map[val]
	if inorder_i < inorder_l or inorder_i > inorder_h:
		return None
	cur = Node(val)
	ind[0] += 1
	cur.left = build(preorder, ind, inorder_l, inorder_i - 1, inorder_map)
	cur.right = build(preorder, ind, inorder_i + 1, inorder_h, inorder_map)
	return cur

def check_same(cur, postorder, ind, res):
	if not cur:
		return
	check_same(cur.left, postorder, ind, res)
	check_same(cur.right, postorder, ind, res)
	if ind[0] == len(postorder):
		res[0] = False
		return
	val = postorder[ind[0]]
	ind[0] += 1
	if cur.data != val:
		res[0] = False
		return
	return True


class Tree:

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

class Solution:

	def checktree(self, preorder, inorder, postorder, N):
		flag = [False]

		def rec1(a, b):
			if flag[0]:
				return None
			if not a:
				return None
			ele = b.pop(0)
			if ele not in a:
				flag[0] = True
				return None
			ind = a.index(ele)
			node = Tree(ele)
			node.left = rec1(a[:ind], b)
			node.right = rec1(a[ind + 1:], b)
			return node

		def rec2(a, b):
			if flag[0]:
				return None
			if not a:
				return None
			ele = b.pop(0)
			if ele not in a:
				flag[0] = True
				return None
			ind = a.index(ele)
			node = Tree(ele)
			node.right = rec2(a[ind + 1:], b)
			node.left = rec2(a[:ind], b)
			return node
		root1 = rec1(inorder, preorder)
		root2 = rec2(inorder, postorder[::-1])

		def identicalTrees(a, b):
			if a is None and b is None:
				return True
			if a is not None and b is not None:
				return a.data == b.data and identicalTrees(a.left, b.left) and identicalTrees(a.right, b.right)
			return False
		if identicalTrees(root1, root2) and (not flag[0]):
			return True
		return False