foldable binary tree

June 23, 2019

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));

    }
}