# foldable binary tree

A Tree is said to be foldable if its left and right counter part can be made to overlap with each other .

For eg – The above tree is foldable . that is, left and right subtree are structurally mirror image of each other. For the 2 to be structurally mirror image, there value need not be the same but the structure needs to be the same. The above tree is not Foldable.

Let’s dig in it’s code now –

```class Node {
int data;
Node left, right;

public Node(int item) {
data = item;
left = right = null;
}
public Node() {
data = 0;
left = right = null;
}
}

// Binary tree Class
class BTree {

static Node root;
static boolean isFoldableTree(Node node) {
if (node == null) {
return true;
}
return isFoldable(node.left, node.right);
}

static boolean isFoldable(Node nodeLeft, Node nodeRight) {

//Check both left and right node is null, if yes then that is fine, return true.
if (nodeLeft == null && nodeRight == null) {
return true;
}
//If one is present and other is null, return false.
if (nodeLeft == null || nodeRight == null) {
return false;
}
// The most Important step is -> when you are Checking if it is structurally a mirror image ,
// Send the left child of left subtree and right child of right subtree //   together. Similarly,
// send the right child of left subtree and left child of right subtree.
boolean left = isFoldable(nodeLeft.left, nodeRight.right);
boolean right = isFoldable(nodeLeft.right, nodeRight.left);

return (left && right);
}

public static void main(String[] args) {
BTree tree = new BTree();
tree.root = new Node(1);
tree.root.left = new Node(5);
tree.root.right = new Node(4);
tree.root.left.left = new Node(9);
tree.root.left.right = new Node(7);
tree.root.right.left = new Node(10);
tree.root.right.right = new Node(13);
System.out.println(" The Symmetry of tree is " + tree.isFoldableTree(root));

}
}
```