Skip to main content

Check for foldable binary tree in python

Python program for Check for foldable binary tree. Here more information.

#  Python 3 program for
#  Check if binary tree is foldable binary tree
#  Using recursion

#  Binary Tree Node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	def isFoldable(self, leftRoot, rightRoot) :
		if (leftRoot == None and rightRoot == None) :
			#  When both node empty
			return True
		elif (leftRoot != None and rightRoot != None and 
              self.isFoldable(leftRoot.left, rightRoot.right) and 
        self.isFoldable(leftRoot.right, rightRoot.left)) :
			#  When
			#  Valid the properties of foldable tree
			return True
		
		#  Fail case
		return False
	
	#  Display tree element inorder form
	def inorder(self, node) :
		if (node != None) :
			#  Visit to left subtree
			self.inorder(node.left)
			#  Print node value
			print("", node.data, end = " ")
			#  Visit to right subtree
			self.inorder(node.right)
		
	

def main() :
	#  Create new tree
	tree = BinaryTree()
	#   Binary Tree
	#  -----------------------
	#       5
	#     /   \
	#    7     4
	#   /       \
	#  1         2
	#   \       /
	#    2     5
	#  Binary tree nodes
	tree.root = TreeNode(5)
	tree.root.left = TreeNode(7)
	tree.root.right = TreeNode(4)
	tree.root.left.left = TreeNode(1)
	tree.root.right.right = TreeNode(2)
	tree.root.right.right.left = TreeNode(5)
	tree.root.left.left.right = TreeNode(2)
	#  Display Tree elements
	tree.inorder(tree.root)
	result = tree.isFoldable(tree.root.left, 
                             tree.root.right)
	if (result == True) :
		print("\n Foldable Tree")
	else :
		print("\n Not Foldable Tree")
	
	#         5
	#       /   \
	#      7     4
	#     /       \
	#    1         2
	#     \       /
	#      2     5
	#       \
	#        3  
	#  Case 2
	tree.root.left.left.right.right = TreeNode(3)
	tree.inorder(tree.root)
	result = tree.isFoldable(tree.root.left, 
                             tree.root.right)
	if (result == True) :
		print("\n Foldable Tree")
	else :
		print("\n Not Foldable Tree")
	

if __name__ == "__main__": main()

Output

 1  2  7  5  4  5  2
 Foldable Tree
 1  2  3  7  5  4  5  2
 Not Foldable Tree




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment