Python_guide/BinaryTree1.py at master · SaiVaniPatil/Python_guide · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# A binary tree node
class Node:

	# Constructor to create a new node
	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

	def __repr__(self):
		return str(self.data)

# Recursive function to check if two given binary trees are identical or not
def isIdentical(root1, root2):
	# If both tree is null return true
	if not root1 and not root2:
		return True

	# if both trees are non-empty and value of their root node matches,
	# recur for their left and right sub-tree
	if (root1 and root2) and (root1.data == root2.data) :
		return isIdentical(root1.left, root2.left) and \
			   isIdentical(root1.right , root2.right)
	else:
		return False

if __name__ == '__main__':
	root1 = Node(1)
	root1.left = Node(2)
	root1.right = Node(3)
	root1.left.left = Node(4)
	root1.left.right = Node(5)
	root1.left.right.left = Node(8)
	root1.left.right.left.left = Node(9)
	root1.left.right.left.left.left = Node(10)
	root1.right.right = Node(7)
	root1.right.right.right = Node(11)

	root2 = Node(1)
	root2.left = Node(2)
	root2.right = Node(3)
	root2.left.left = Node(4)
	root2.left.right = Node(5)
	root2.left.right.left = Node(8)
	root2.left.right.left.left = Node(9)
	root2.left.right.left.left.left = Node(10)
	root2.right.right = Node(7)
	root2.right.right.right = Node(11)

	print("root1 and root2 are Identical " if isIdentical(root1, root2)
		  else "root1 and root2 are not Identical ")

	root1.right.right.right = Node(12)
	print("root1 and root2 are Identical " if isIdentical(root1, root2)
		  else "root1 and root2 are not Identical ")

# This code is contributed by Sumit Bhardwaj