Check whether Binary Tree is foldable or not.

Given a binary tree, Check if tree can be folded or not?Java Program to Check whether Tree is foldable.

---

Check whether given binary tree can be folded or not.

Lets see what is the input and expected output for better understanding on Foldable Binary Tree.

Check if tree is foldable or not

Algorithm

---

Binary Tree is said to be Foldable if nodes of Left and Right Subtree are exact mirror of each other.

Step 1: Traverse Binary Tree and compare left node of Left subtree with right node of Right subtree.

Step 2: Traverse Binary Tree and compare right node of Left subtree with left node of Right subtree.

Step 3: 
In both steps 1 and 2 above, check both left and right node is null or both left and right node is not null, if Yes, then Tree is foldable and has identitical structure otherwise not.
 
Note: To check whether Tree is Foldable, we will not be looking at data of the nodes and concentrate only on structure of Tree.

Algorithm to check whether Tree is foldable is very similar to algorithm for Checking whether Binary Trees are Mirror of each other.
Check a given two Binary Trees are Mirror of each other.

Java Program to Check whether Tree is foldable.

---

package javabypatel.tree;

public class FoldableBinaryTree {

 public static void main(String[] args) {
  new FoldableBinaryTree();
 }

 public FoldableBinaryTree(){
  Node rootNode=null;

  rootNode  = addNode(rootNode, 10, true);
  rootNode  = addNode(rootNode, 2, true);
  rootNode  = addNode(rootNode, 1, true);
  rootNode  = addNode(rootNode, 3, true);
  rootNode  = addNode(rootNode, 15, true);
  rootNode  = addNode(rootNode, 14, true);
  rootNode  = addNode(rootNode, 16, true);

  System.out.println(isFoldableBinaryTree(rootNode));
 }

 private boolean isFoldableBinaryTree(Node rootNode) {
  if(rootNode==null){
   return true;
  }
  return isFoldableBinaryTreeUtil(rootNode.getLeft(), rootNode.getRight()); 
 }
 
 private boolean isFoldableBinaryTreeUtil(Node rootNodeLeft, Node rootNodeRight) {
  
  //Check both left and right node is null, if yes then that is fine, return true.
  if(rootNodeLeft == null && rootNodeRight == null){
   return true;
  }
  
  //Control reach to this point only in 2 conditions,
  //1. Either of left or right node is null (not both as we did that check above).
  //2. left and right both node is not null. (that is fine)
  //So if we found either of left or right node is null, we return false;(check point 1 in above case) 
  if(rootNodeLeft == null || rootNodeRight == null){
   return false;
  }
  
  boolean left = isFoldableBinaryTreeUtil(rootNodeLeft.getLeft(), rootNodeRight.getRight());
  boolean right = isFoldableBinaryTreeUtil(rootNodeLeft.getRight(), rootNodeRight.getLeft());
  
  //If both of Left and Right subtree return true then only return true else return false.
  return left && right;
 }
 
 private static Node addNode(Node rootNode, int i, boolean isRootNode) {
  if(rootNode==null){
   return new Node(i);
  }else{
   if(i > rootNode.getData()){
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }

   }else{
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }
   }
  }
  return rootNode;
 }
}

Node.java

package javabypatel.tree;

public class Node{
 private Node left;
 private Node right;
 private int data;
 
 public Node(int data){
  this.data=data;
 }
 public Node getLeft() {
  return left;
 }
 public void setLeft(Node left) {
  this.left = left;
 }
 public Node getRight() {
  return right;
 }
 public void setRight(Node right) {
  this.right = right;
 }
 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
}

You may also like to see

---

Top Binary tree interview questions in Java

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.

Serialize and Deserialize a Binary Tree

---

Compress a given string in-place and with constant extra space.

Check whether a given string is an interleaving of String 1 and String 2.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Advanced Multithreading Interview Questions In Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.