Skip to main content

Check for foldable binary tree in java

Java program for Check for foldable binary tree. Here problem description and explanation.

/* 
  Java program for
  Check if binary tree is foldable binary tree
  Using recursion
*/
// Binary Tree Node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root
        this.root = null;
    }
    public boolean isFoldable(TreeNode leftRoot, 
                              TreeNode rightRoot)
    {
        if (leftRoot == null && rightRoot == null)
        {
            // When both node empty
            return true;
        }
        else if (leftRoot != null && rightRoot != null && 
                isFoldable(leftRoot.left, rightRoot.right) && 
                isFoldable(leftRoot.right, rightRoot.left))
        {
            // When 
            // Valid the properties of foldable tree 
            return true;
        }
        // Fail case
        return false;
    }
    // Display tree element inorder form
    public void inorder(TreeNode node)
    {
        if (node != null)
        {
            // Visit to left subtree
            inorder(node.left);
            // Print node value
            System.out.print("  " + node.data);
            // Visit to right subtree
            inorder(node.right);
        }
    }
    public static void main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*
           Binary Tree
          -----------------------
               5
             /   \
            7     4
           /       \
          1         2
           \       /
            2     5
        */
        // Binary tree nodes
        tree.root = new TreeNode(5);
        tree.root.left = new TreeNode(7);
        tree.root.right = new TreeNode(4);
        tree.root.left.left = new TreeNode(1);
        tree.root.right.right = new TreeNode(2);
        tree.root.right.right.left = new TreeNode(5);
        tree.root.left.left.right = new TreeNode(2);
        // Display Tree elements
        tree.inorder(tree.root);
        boolean result = tree.isFoldable(tree.root.left, 
                                         tree.root.right);
        if (result == true)
        {
            System.out.println("\n Foldable Tree");
        }
        else
        {
            System.out.println("\n Not Foldable Tree");
        }
        /*
                 5
               /   \
              7     4
             /       \
            1         2
             \       /
              2     5
               \
                3  
        */
        // Case 2
        tree.root.left.left.right.right = new TreeNode(3);
        tree.inorder(tree.root);
        result = tree.isFoldable(tree.root.left, tree.root.right);
        if (result == true)
        {
            System.out.println("\n Foldable Tree");
        }
        else
        {
            System.out.println("\n Not Foldable Tree");
        }
    }
}

Output

  1  2  7  5  4  5  2
 Foldable Tree
  1  2  3  7  5  4  5  2
 Not Foldable Tree




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment