











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)); } }
Login/Signup to comment