Folding BSTs

Given a binary tree, find out if the tree can be folded or not.

Eg : tree (a) can be folded, but (b) cannot be folded

(a)    10
    /       \
  7         15
   \        /
    9   11 

(b)
      10
    /     \
   7     15
  /      /
 5     11

The tree can be folded only if its left subtree is mirror image of its right subtree or vice versa( considering their organization only not node valves.)

Geeks for Geeks – has two solutions from which I like solution 2.

Method 2 (Check if Left and Right subtrees are Mirror)
There are mainly two functions:

// Checks if tree can be folded or not

IsFoldable(root)
1) If tree is empty then return true
2) Else check if left and right subtrees are structure wise mirrors of
    each other. Use utility function IsFoldableUtil(root->left,
    root->right) for this.

// Checks if n1 and n2 are mirror of each other.

IsFoldableUtil(n1, n2)

1) If both trees are empty then return true.

2) If one of them is empty and other is not then return false.

3) Return true if following conditions are met

   a) n1->left is mirror of n2->right

   b) n1->right is mirror of n2->left
Sample Java implementation :
public class FoldableTree {

 public boolean isFoldable(Node node)
 {
     if(node==null)
        return true;
     else
        return isFoldable(node.left, node.right);
 }
 public boolean isFoldable(Node n1, Node n2){
    /* If both left and right subtrees are NULL,
       then return true */
     if (n1 == null && n2 == null)
         return true;  
    
    /* If one of the trees is NULL and other is not,
       then return false */
     if (n1 == null || n2 == null)
         return false; 
  
    /* Otherwise check if left and right subtrees are mirrors of
       their counterparts */
    return isFoldable(n1.left, n2.right) && isFoldable(n1.right, n2.left);
 
 }
 public static void main(String[] args) {
 
 FoldableTree tree = new FoldableTree();
 /* The constructed binary tree is
    1
  /   \
 2     3
  \    /
   4  5
 */
 Node root        = new Node(1);
 root.left        = new Node(2);
 root.right       = new Node(3);
 root.left.right  = new Node(4);
 root.right.left  = new Node(5);

 if(tree.isFoldable(root) == true)
     System.out.println("tree is foldable"); 
 else
     System.out.println("tree is not foldable"); 

 }
}//:~