Posted on by Kalkicode
Code Binary Tree

# Check for foldable binary tree in python

``````#  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.

Categories
Relative Post