Foldable Binary Trees

Last Updated : 13 Jan, 2023

Given a binary tree, find out if the tree can be folded or not. A tree can be folded if the left and right subtrees of the tree are structure-wise mirror images of each other. An empty tree is considered foldable.

Examples:

Input:
10
/ \
7 15
\ /
9 11
Output: Can be folded

Input:
10
/ \
7 15
/ /
5 11
Output: Cannot be folded

Recommended PracticeFoldable Binary TreeTry It!

Foldable Binary Trees by Changing Left Subtree to its Mirror:

The idea is to change the left subtree to its mirror then check that left subtree with its right subtree.

Follow the steps below to solve the problem:

If tree is empty, then return true.
Convert the left subtree to its mirror image
Check if the structure of left subtree and right subtree is same and store the result.
- res = isStructSame(root->left, root->right). isStructSame() recursively compares structures of two subtrees and returns true if structures are same
Revert the changes made in step (2) to get the original tree.
Return result res stored in step 3.

Below is the implementation of the above approach.

C++

// C++ program to check foldable binary tree
#include <bits/stdc++.h>
using namespace std;
 
/* You would want to remove below
3 lines if your compiler supports
bool, true and false */
 
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;
};
 
/* converts a tree to its mirror image */
void mirror(node* node);
 
/* returns true if structure of
two trees a and b is same only
structure is considered for comparison, not data! */
bool isStructSame(node* a, node* b);
 
/* Returns true if the given tree is foldable */
bool isFoldable(node* root)
{
    bool res;
 
    /* base case */
    if (root == NULL)
        return true;
 
    /* convert left subtree to its mirror */
    mirror(root->left);
 
    /* Compare the structures of the
    right subtree and mirrored
    left subtree */
    res = isStructSame(root->left, root->right);
 
    /* Get the original tree back */
    mirror(root->left);
 
    return res;
}
 
bool isStructSame(node* a, node* b)
{
    if (a == NULL && b == NULL) {
        return true;
    }
    if (a != NULL && b != NULL
        && isStructSame(a->left, b->left)
        && isStructSame(a->right, b->right)) {
        return true;
    }
 
    return false;
}
 
/* UTILITY FUNCTIONS */
/* Change a tree so that the roles of the left and
    right pointers are swapped at every node.
    See https:// www.geeksforgeeks.org/?p=662 for details */
void mirror(node* Node)
{
    if (Node == NULL)
        return;
    else {
        node* temp;
 
        /* do the subtrees */
        mirror(Node->left);
        mirror(Node->right);
 
        /* swap the pointers in this node */
        temp = Node->left;
        Node->left = Node->right;
        Node->right = temp;
    }
}
 
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return (Node);
}
 
/* Driver program to test mirror() */
int main(void)
{
    /* The constructed binary tree is
            1
        / \
        2 3
        \ /
        4 5
    */
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->right->left = newNode(5);
 
    if (isFoldable(root) == 1) {
        cout << "tree is foldable";
    }
    else {
        cout << "\ntree is not foldable";
    }
    return 0;
}
 
// This code is contributed by rathbhupendra

C

#include <stdio.h>
#include <stdlib.h>
 
/* You would want to remove below 3 lines if your compiler
   supports bool, true and false */
#define bool int
#define true 1
#define false 0
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* converts a tree to its mirror image */
void mirror(struct node* node);
 
/* returns true if structure of two trees a and b is same
   Only structure is considered for comparison, not data! */
bool isStructSame(struct node* a, struct node* b);
 
/* Returns true if the given tree is foldable */
bool isFoldable(struct node* root)
{
    bool res;
 
    /* base case */
    if (root == NULL)
        return true;
 
    /* convert left subtree to its mirror */
    mirror(root->left);
 
    /* Compare the structures of the right subtree and
    mirrored left subtree */
    res = isStructSame(root->left, root->right);
 
    /* Get the original tree back */
    mirror(root->left);
 
    return res;
}
 
bool isStructSame(struct node* a, struct node* b)
{
    if (a == NULL && b == NULL) {
        return true;
    }
    if (a != NULL && b != NULL
        && isStructSame(a->left, b->left)
        && isStructSame(a->right, b->right)) {
        return true;
    }
 
    return false;
}
 
/* UTILITY FUNCTIONS */
/* Change a tree so that the roles of the  left and
    right pointers are swapped at every node.
    See https:// www.geeksforgeeks.org/?p=662 for details */
void mirror(struct node* node)
{
    if (node == NULL)
        return;
    else {
        struct node* temp;
 
        /* do the subtrees */
        mirror(node->left);
        mirror(node->right);
 
        /* swap the pointers in this node */
        temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
/* Driver program to test mirror() */
int main(void)
{
    /* The constructed binary tree is
         1
       /   \
      2     3
      \    /
       4  5
  */
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(4);
    root->left->right = newNode(5);
 
    if (isFoldable(root) == 1) {
        printf("\n tree is foldable");
    }
    else {
        printf("\n tree is not foldable");
    }
 
    getchar();
    return 0;
}

Java

// Java program to check foldable binary tree
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
class Node {
    int data;
    Node left, right;
 
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
    Node root;
 
    /* Returns true if the given tree is foldable */
    boolean isFoldable(Node node)
    {
        boolean res;
 
        /* base case */
        if (node == null)
            return true;
 
        /* convert left subtree to its mirror */
        mirror(node.left);
 
        /* Compare the structures of the right subtree and
         mirrored left subtree */
        res = isStructSame(node.left, node.right);
 
        /* Get the original tree back */
        mirror(node.left);
 
        return res;
    }
 
    boolean isStructSame(Node a, Node b)
    {
        if (a == null && b == null)
            return true;
        if (a != null && b != null
            && isStructSame(a.left, b.left)
            && isStructSame(a.right, b.right))
            return true;
 
        return false;
    }
 
    /* UTILITY FUNCTIONS */
 
    /* Change a tree so that the roles of the  left and
       right pointers are swapped at every node.
       See https:// www.geeksforgeeks.org/?p=662 for details
     */
    void mirror(Node node)
    {
        if (node == null)
            return;
        else {
            Node temp;
 
            /* do the subtrees */
            mirror(node.left);
            mirror(node.right);
 
            /* swap the pointers in this node */
            temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
    }
 
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
 
        /* The constructed binary tree is
             1
           /   \
          2     3
           \    /
            4  5
        */
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.right.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        if (tree.isFoldable(tree.root))
            System.out.println("tree is foldable");
        else
            System.out.println("Tree is not foldable");
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 program to check foldable binary tree
 
#  A binary tree node has data,
# pointer to left child and a
# pointer to right child
 
 
class newNode:
    def __init__(self, d):
        self.data = d
        self.left = None
        self.right = None
 
# Returns true if the given
# tree is foldable
 
 
def isFoldable(node):
 
    # base case
    if node == None:
        return true
 
    # convert left subtree to its mirror
    mirror(node.left)
 
    # Compare the structures of the right subtree and mirrored
    # left subtree
    res = isStructSame(node.left, node.right)
 
    # Get the original tree back
    mirror(node.left)
 
    return res
 
 
def isStructSame(a, b):
 
    if a == None and b == None:
        return True
    if a != None and b != None and isStructSame(a.left, b.left) and isStructSame(a.right, b.right):
        return True
 
    return False
 
 
def mirror(node):
 
    if node == None:
        return
    else:
 
        # do the subtrees
        mirror(node.left)
        mirror(node.right)
 
        # swap the pointers in this node
        temp = node.left
        node.left = node.right
        node.right = temp
 
 
# Driver Code
if __name__ == '__main__':
 
    ''' 
    The constructed binary tree is
             1
           /   \
          2     3
           \    /
            4  5
    '''
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.right.left = newNode(4)
    root.left.right = newNode(5)
 
    if isFoldable(root):
        print("tree is foldable")
    else:
        print("Tree is not foldable")

C#

// C# program to check foldable
// binary tree
using System;
 
/* A binary tree node has data,
pointer to left child and
a pointer to right child */
class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
    Node root;
 
    /* Returns true if the given
   tree is foldable */
    Boolean isFoldable(Node node)
    {
        Boolean res;
 
        /* base case */
        if (node == null)
            return true;
 
        /* convert left subtree
       to its mirror */
        mirror(node.left);
 
        /* Compare the structures of the
       right subtree and mirrored
       left subtree */
        res = isStructSame(node.left, node.right);
 
        /* Get the original tree back */
        mirror(node.left);
 
        return res;
    }
 
    Boolean isStructSame(Node a, Node b)
    {
        if (a == null && b == null)
            return true;
        if (a != null && b != null
            && isStructSame(a.left, b.left)
            && isStructSame(a.right, b.right))
            return true;
 
        return false;
    }
 
    /* UTILITY FUNCTIONS */
 
    /* Change a tree so that the roles
of the left and right pointers are
swapped at every node.
See https:// www.geeksforgeeks.org/?p=662
for details */
    void mirror(Node node)
    {
        if (node == null)
            return;
        else {
            Node temp;
 
            /* do the subtrees */
            mirror(node.left);
            mirror(node.right);
 
            /* swap the pointers in this node */
            temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
    }
 
    // Driver Code
    static public void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        /* The constructed binary tree is
                    1
                 /     \
                2        3
                 \     /
                 4    5
    */
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.right.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        if (tree.isFoldable(tree.root))
            Console.WriteLine("tree is foldable");
        else
            Console.WriteLine("Tree is not foldable");
    }
}
 
// This code is contributed by Arnab Kundu

Javascript

<script>
 
class Node
{
    constructor(item)
    {
        this.data=item;
        this.left=this.right=null;
         
    }
}
 
function isFoldable(node)
{
    let res;
  
        /* base case */
        if (node == null)
            return true;
  
        /* convert left subtree to its mirror */
        mirror(node.left);
  
        /* Compare the structures of the right subtree and mirrored
         left subtree */
        res = isStructSame(node.left, node.right);
  
        /* Get the original tree back */
        mirror(node.left);
  
        return res;
}
 
function isStructSame(a,b)
{
    if (a == null && b == null)
            return true;
        if (a != null && b != null
            && isStructSame(a.left, b.left)
            && isStructSame(a.right, b.right))
            return true;
  
        return false;
}
 
function mirror(node)
{
    if (node == null)
            return;
        else {
            let temp;
  
            /* do the subtrees */
            mirror(node.left);
            mirror(node.right);
  
            /* swap the pointers in this node */
            temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
}
 
/* The constructed binary tree is
             1
           /   \
          2     3
           \    /
            4  5
        */
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.left.right = new Node(5);
 
if (isFoldable(root))
    document.write("tree is foldable");
else
    document.write("Tree is not foldable");
 
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output

tree is foldable

Time complexity: O(N), Visiting all the nodes of the tree of size N.
Auxiliary Space: O(N), If stack space is considered else O(1)

Thanks to ajaym for suggesting this approach.

Foldable Binary Trees by Checking if Left and Right subtrees are Mirror:

The idea is to check the left and right subtree whether they are mirror or not.

Follow the steps below to solve the problem:

If tree is empty then return true.
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.
- If both trees are empty then return true.
- If one of them is empty and other is not then return false.
- Return true if following conditions are met
  - n1->left is mirror of n2->right
  - n1->right is mirror of n2->left

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>
using namespace std;
 
/* You would want to remove below 3 lines if your compiler
supports bool, true and false */
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;
};
 
/* A utility function that checks
if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldableUtil(node* n1, node* n2);
 
/* Returns true if the given tree can be folded */
bool IsFoldable(node* root)
{
    if (root == NULL) {
        return true;
    }
 
    return IsFoldableUtil(root->left, root->right);
}
 
/* A utility function that checks
if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldableUtil(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 IsFoldableUtil(n1->left, n2->right)
           && IsFoldableUtil(n1->right, n2->left);
}
 
/*UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return (Node);
}
 
/* Driver code */
int main(void)
{
    /* The constructed binary tree is
        1
        / \
        2 3
        \ /
        4 5
    */
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->right->left = newNode(5);
 
    if (IsFoldable(root) == true) {
        cout << "tree is foldable";
    }
    else {
        cout << "tree is not foldable";
    }
 
    return 0;
}
 
// This is code is contributed by rathbhupendra

C

#include <stdio.h>
#include <stdlib.h>
 
/* You would want to remove below 3 lines if your compiler
   supports bool, true and false */
#define bool int
#define true 1
#define false 0
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* A utility function that checks if trees with roots as n1
  and n2 are mirror of each other */
bool IsFoldableUtil(struct node* n1, struct node* n2);
 
/* Returns true if the given tree can be folded */
bool IsFoldable(struct node* root)
{
    if (root == NULL) {
        return true;
    }
 
    return IsFoldableUtil(root->left, root->right);
}
 
/* A utility function that checks if trees with roots as n1
  and n2 are mirror of each other */
bool IsFoldableUtil(struct node* n1, struct 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 IsFoldableUtil(n1->left, n2->right)
           && IsFoldableUtil(n1->right, n2->left);
}
 
/*UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
/* Driver program to test mirror() */
int main(void)
{
    /* The constructed binary tree is
         1
       /   \
      2     3
      \    /
       4  5
  */
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->right->left = newNode(5);
 
    if (IsFoldable(root) == true) {
        printf("\n tree is foldable");
    }
    else {
        printf("\n tree is not foldable");
    }
 
    getchar();
    return 0;
}

Java

// Java program to check foldable binary tree
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
class Node {
    int data;
    Node left, right;
 
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
    Node root;
 
    /* Returns true if the given tree can be folded */
    boolean IsFoldable(Node node)
    {
        if (node == null)
            return true;
 
        return IsFoldableUtil(node.left, node.right);
    }
 
    /* A utility function that checks if trees with roots as
     n1 and n2 are mirror of each other */
    boolean IsFoldableUtil(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 IsFoldableUtil(n1.left, n2.right)
            && IsFoldableUtil(n1.right, n2.left);
    }
 
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
 
        /* The constructed binary tree is
             1
           /   \
          2     3
           \    /
            4  5
        */
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.right.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        if (tree.IsFoldable(tree.root))
            System.out.println("tree is foldable");
        else
            System.out.println("Tree is not foldable");
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 program to check
# foldable binary tree
 
# Utility function to create a new
# tree node
 
 
class newNode:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None
 
# Returns true if the given tree can be folded
 
 
def IsFoldable(root):
    if (root == None):
        return True
    return IsFoldableUtil(root.left, root.right)
 
 
# A utility function that checks
# if trees with roots as n1 and n2
# are mirror of each other
def IsFoldableUtil(n1, n2):
    # If both left and right subtrees are NULL,
    # then return true
    if n1 == None and n2 == None:
        return True
 
    # If one of the trees is NULL and other is not,
    # then return false
    if n1 == None or n2 == None:
        return False
 
    # Otherwise check if left and
    # right subtrees are mirrors of
    # their counterparts
 
    d1 = IsFoldableUtil(n1.left, n2.right)
    d2 = IsFoldableUtil(n1.right, n2.left)
    return d1 and d2
 
 
# Driver code
if __name__ == "__main__":
 
    """ The constructed binary tree is  
    1  
    / \  
    2 3  
    \ /  
    4 5  
"""
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.right = newNode(4)
    root.right.left = newNode(5)
 
    if IsFoldable(root):
        print("tree is foldable")
    else:
        print("tree is not foldable")
 
# This code is contributed by
# Anupam Baranwal(anupambaranwal)

C#

// C# program to check foldable binary tree
using System;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    Node root;
 
    /* Returns true if the given tree can be folded */
    bool IsFoldable(Node node)
    {
        if (node == null)
            return true;
 
        return IsFoldableUtil(node.left, node.right);
    }
 
    /* A utility function that checks if
    trees with roots as n1 and n2
    are mirror of each other */
    bool IsFoldableUtil(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 IsFoldableUtil(n1.left, n2.right)
            && IsFoldableUtil(n1.right, n2.left);
    }
 
    /* Driver code */
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        /* The constructed binary tree is
            1
        / \
        2     3
        \ /
            4 5
        */
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.right.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        if (tree.IsFoldable(tree.root))
            Console.WriteLine("tree is foldable");
        else
            Console.WriteLine("Tree is not foldable");
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
    // JavaScript program to check foldable binary tree
     
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
 
    let root;
  
    /* Returns true if the given tree can be folded */
    function IsFoldable(node)
    {
        if (node == null)
            return true;
  
        return IsFoldableUtil(node.left, node.right);
    }
  
    /* A utility function that checks if trees with roots as
     n1 and n2 are mirror of each other */
    function IsFoldableUtil(n1, 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 IsFoldableUtil(n1.left, n2.right)
            && IsFoldableUtil(n1.right, n2.left);
    }
     
    /* The constructed binary tree is
             1
           /   \
          2     3
           \    /
            4  5
        */
    root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.right.left = new Node(4);
    root.left.right = new Node(5);
 
    if (IsFoldable(root))
      document.write("tree is foldable");
    else
      document.write("Tree is not foldable");
     
</script>

Output

tree is foldable

Time Complexity: O(N), Visiting every node of the tree of size N.
Auxiliary Space: O(N), If stack space is considered

Foldable Binary Trees using Breadth first Search:

The idea is to use Queue for traversing the tree and using the BFS approach.

Follow the steps below to solve the problem:

The left child of the left subtree = the right child of the right subtree. Both of them should be not null.
The right child of the left subtree = left child of the right subtree. Both of them should be null or not null.

Below is the implementation of the above approach:

C++

// CPP code for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Class Node to store the data and left and right
// pointers
class Node
{
public:
    int key;
    Node *left;
    Node *right;
 
    Node(int key)
    {
        this->key = key;
        left = right = NULL;
    }
};
 
class FoldableTrees
{
public:
    Node *root = NULL;
 
    // Function to find whether the tree is foldable
    bool isFoldable()
    {
 
        // Queue to store visited nodes
        queue<Node *> q;
 
        // Initially add the left and right nodes of root
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
 
        while (!q.empty())
        {
 
            // Remove the front 2 nodes to
            // check for null condition
            Node *p = q.front();
            q.pop();
            Node *r = q.front();
            q.pop();
 
            // If both are null, continue and check
            // the further elements
            if (p == NULL && r == NULL)
                continue;
 
            // If one of them is not null, then return false
            if ((p == NULL && r != NULL) || (p != NULL && r == NULL))
                return false;
 
            /* Insert in the same order:
            1. left of left subtree
            2. right of right subtree
            3.right of left subtree
            4.left of right subtree */
            q.push(p->left);
            q.push(r->right);
            q.push(p->right);
            q.push(r->left);
        }
 
        // Only if the tree is foldable
        return true;
    }
 
    // Driver code
};
 
int main()
{
    FoldableTrees tree = FoldableTrees();
 
    // Insert data into the tree
    tree.root = new Node(1);
    tree.root->left = new Node(2);
    tree.root->right = new Node(3);
    tree.root->right->left = new Node(4);
    tree.root->left->right = new Node(5);
 
    // Function call
    if (tree.isFoldable())
        cout << "tree is foldable" << endl;
    else
        cout << "tree is not foldable" << endl;
}
 
// This code is contributed by adityamaharshi21

Java

// Java code for the above approach
 
import java.util.LinkedList;
import java.util.Queue;
 
public class FoldableTrees {
    Node root = null;
 
     
    class Node {
        int key;
        Node left;
        Node right;
 
        Node(int key)
        {
            this.key = key;
            left = right = null;
        }
    }
 
    // Function to find whether the tree is foldable
    boolean isFoldable()
    {
 
        // Queue to store visited nodes
        Queue<Node> q = new LinkedList<>();
 
        // Initially add the left and right nodes of root
        if (root != null) {
            q.add(root.left);
            q.add(root.right);
        }
 
        while (!q.isEmpty()) {
 
            // Remove the front 2 nodes to
            // check for null condition
            Node p = q.remove();
            Node r = q.remove();
 
            // If both are null, continue and check
            // the further elements
            if (p == null && r == null)
                continue;
 
            // If one of them is not null, then return false
            if ((p == null && r != null)
                || (p != null && r == null))
                return false;
 
            /* Insert in the same order:
              1. left of left subtree
              2. right of right subtree
              3.right of left subtree
              4.left of right subtree  */
            q.add(p.left);
            q.add(r.right);
            q.add(p.right);
            q.add(r.left);
        }
 
        // Only if the tree is foldable
        return true;
    }
 
    // Driver code
    public static void main(String args[])
    {
        FoldableTrees tree = new FoldableTrees();
 
        // Insert data into the tree
        tree.root = tree.new Node(1);
        tree.root.left = tree.new Node(2);
        tree.root.right = tree.new Node(3);
        tree.root.right.left = tree.new Node(4);
        tree.root.left.right = tree.new Node(5);
 
        // Function call
        if (tree.isFoldable())
            System.out.println("tree is foldable");
        else
            System.out.println("tree is not foldable");
    }
}
 
// This method is contributed by likhita AVL

Python3

# class to create a node with key, left child and right child.
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
 
# Function to find whether the tree is foldable
def isFoldable(root):
 
     # Queue to store visited nodes
    q = []
 
    # Initially add the left and right nodes of root
    if root != None:
        q.append(root.left)
        q.append(root.right)
 
    while (len(q) != 0):
 
        # Remove the front 2 nodes to
        # check for None condition
        p = q.pop(0)
        r = q.pop(0)
 
        # If both are None, continue and check
        # the further elements
        if (p == None and r == None):
            continue
 
        # If one of them is not None, then return False
        if ((p == None and r != None) or (p != None and r == None)):
            return False
 
        ''' Insert in the same order:
            1. left of left subtree
            2. right of right subtree
            3. right of left subtree
            4. left of right subtree  
        '''
        q.append(p.left)
        q.append(r.right)
        q.append(p.right)
        q.append(r.left)
 
    # Only if the tree is foldable
    return True
 
 
# Driver code
# Insert data into the tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.left.right = Node(5)
 
# Function call
if isFoldable(root):
    print("tree is foldable")
else:
    print("tree is not foldable")
 
    # This code is contributed by mariuscristiancapatina

C#

using System;
using System.Collections.Generic;
 
public class Node {
    public int key;
    public Node left, right;
 
    public Node(int key)
    {
        this.key = key;
        this.left = this.right = null;
    }
}
 
public class FoldableTrees {
    Node root = null;
 
    // Function to find whether the tree is foldable
    bool isFoldable()
    {
 
        // Queue to store visited nodes
        Queue<Node> q = new Queue<Node>();
 
        // Initially add the left and right nodes of root
        if (root != null) {
            q.Enqueue(root.left);
            q.Enqueue(root.right);
        }
 
        while (q.Count != 0) {
 
            // Remove the front 2 nodes to
            // check for null condition
            Node p = q.Dequeue();
            Node r = q.Dequeue();
 
            // If both are null, continue and check
            // the further elements
            if (p == null && r == null)
                continue;
 
            // If one of them is not null, then return false
            if ((p == null && r != null)
                || (p != null && r == null))
                return false;
 
            /* Insert in the same order:
              1. left of left subtree
              2. right of right subtree
              3.right of left subtree
              4.left of right subtree  */
            q.Enqueue(p.left);
            q.Enqueue(r.right);
            q.Enqueue(p.right);
            q.Enqueue(r.left);
        }
 
        // Only if the tree is foldable
        return true;
    }
 
    // Driver code
    static public void Main()
    {
        FoldableTrees tree = new FoldableTrees();
 
        // Insert data into the tree
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.right.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        // Function call
        if (tree.isFoldable())
            Console.WriteLine("tree is foldable");
        else
            Console.WriteLine("tree is not foldable");
    }
}
 
// This code is contributed by patel2127.

Javascript

<script>
// Javascript code for the above approach
 
let root = null;
 
// Class Node to store the data and left and right pointers
class Node
{
    constructor(key)
    {
        this.key=key;
        this.left=this.right=null;
    }
}
 
// Function to find whether the tree is foldable
function isFoldable() 
{
     // Queue to store visited nodes
        let q = [];
        
        // Initially add the left and right nodes of root
        if (root != null) {
            q.push(root.left);
            q.push(root.right);
        }
  
        while (q.length!=0) {
            
            // Remove the front 2 nodes to
            // check for null condition
            let p = q.shift();
            let r = q.shift();
            
            // If both are null, continue and check
            // the further elements
            if (p == null && r == null)
                continue;
            
            // If one of them is not null, then return false
            if ((p == null && r != null) || (p != null && r == null))
                return false;
              
              /* Insert in the same order:
                1. left of left subtree
                2. right of right subtree
                3.right of left subtree
                4.left of right subtree  */
            q.push(p.left);
            q.push(r.right);
            q.push(p.right);
            q.push(r.left);
        }
        
        // Only if the tree is foldable
        return true;
}
 
// Driver code
// Insert data into the tree
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.left.right = new Node(5);
 
// Function call
if(isFoldable())
    document.write("Tree is foldable");
else
    document.write("Tree is not foldable");
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

tree is foldable

Time complexity: O(N), Visiting all the nodes of the tree of size N.
Auxiliary Space: O(N), Using queue for storing nodes

Please write comments if you find the above code/algorithm incorrect, or find other ways to solve the same problem.

GeeksforGeeks

Improve

Previous Article

Check if two trees are Mirror

Symmetric Tree (Mirror Image of itself)

Similar Reads

Total number of possible Binary Search Trees and Binary Trees with n keys

Total number of possible Binary Search Trees with n different keys (countBST(n)) = Catalan number Cn = (2n)! / ((n + 1)! * n!) For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, .... So are numbers of Binary Search Trees. Total number of possible Binary Trees with n different keys (countBT(n)) = countBST(n

Introduction to Generic Trees (N-ary Trees)

Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes. Every node stores address of its children and the very first node's address will be stored in a s

Count the Number of Binary Search Trees present in a Binary Tree

Given a binary tree, the task is to count the number of Binary Search Trees present in it. Examples: Input: 1 / \ 2 3 / \ / \ 4 5 6 7 Output: 4Here each leaf node represents a binary search tree and there are total 4 nodes. Input: 11 / \ 8 10 / / \ 5 9 8 / \ 4 6 Output: 6 Sub-tree rooted under node 5 is a BST 5 / \ 4 6 Another BST we have is rooted

Construct a Maximum Binary Tree from two given Binary Trees

Given two Binary Trees, the task is to create a Maximum Binary Tree from the two given binary trees and print the Inorder Traversal of that tree. What is the maximum Binary Tree? The maximum binary is constructed in the following manner: In the case of both the Binary Trees having two corresponding nodes, the maximum of the two values is considered

Data Structures | Binary Trees | Question 1

Which of the following is true about Binary Trees? (A) Every binary tree is either complete or full. (B) Every complete binary tree is also a full binary tree. (C) Every full binary tree is also a complete binary tree. (D) No binary tree is both complete and full. (E) None of the above Answer: (E)Explanation: A full binary tree (sometimes proper bi

Data Structures | Binary Trees | Question 15

If arity of operators is fixed, then which of the following notations can be used to parse expressions without parentheses? a) Infix Notation (Inorder traversal of a expression tree) b) Postfix Notation (Postorder traversal of a expression tree) c) Prefix Notation (Preorder traversal of a expression tree) (A) b and c (B) Only b (C) a, b and c (D) N

Data Structures | Binary Trees | Question 3

What are the main applications of tree data structure? Manipulate hierarchical data Make information easy to search Manipulate sorted lists of data Router algorithms Form of a multi-stage decision-making, like Chess Game. As a workflow for compositing digital images for visual effects (A) 1, 2, 3, 4 and 6 (B) 1, 2, 3, 4 and 5 (C) 1, 3, 4, 5 and 6 (

Data Structures | Binary Trees | Question 4

Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is In the following answers, the operator '^' indicates power. (A) 2^(i-1) (B) 2^i (C) 2^(i+1) (D) 2^[(i+1)/2] Answer: (A) Explanation: Number of nodes of bin

Data Structures | Binary Trees | Question 15

In a complete k-ary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is: (A) nk (B) (n – 1) k+ 1 (C) n( k – 1) + 1 (D) n(k – 1) Answer: (C) Explanation: For an k-ary tree where each node has k children or no children, following relation holds L = (k-1)*n + 1 Where L is the numbe

Data Structures | Binary Search Trees | Question 1

What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree for a skewed tree ? (A) O(n) for all (B) O(Logn) for all (C) O(Logn) for search and insert, and O(n) for delete (D) O(Logn) for search, and O(n) for insert and delete Answer: (A)Explanation: In skewed Binary Search Tree (BST), all three o

Article Tags :

Practice Tags :