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.w3wiki.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.w3wiki.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.w3wiki.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.w3wiki.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 Changing Left Subtree to its Mirror

C++

C

Java

Python3

C#

Javascript

Foldable Binary Trees

Categories

Contact US

Foldable Binary Trees by Changing Left Subtree to its Mirror

C++

C

Java

Python3

C#

Javascript

Foldable Binary Trees

Similar Reads

Categories

Contact US