IdenticalTree(), mirrorTree(), isFoldableTree() and isSumTree()

Same Tree:

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way

http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/
http://www.geeksforgeeks.org/iterative-function-check-two-trees-identical/

int sameTree(struct node* a, struct node* b) { 

int sameTree(struct tree* a, struct tree* b)
{

    if (a==NULL && b==NULL)
        return 1;
    else if (a!=NULL && b!=NULL)
   {
        return
        (
            a->data == b->data &&
           sameTree(a->left, b->left) &&
           sameTree(a->right, b->right)
        );
    }
    else return 0;
}
Time Complexity:
Complexity of the identicalTree() will be according to the tree with lesser number of nodes. Let number of nodes in two trees be m and n then complexity of sameTree() is O(m) where m < n.

Iterative solution:

If they are binary search trees then you can do any kind of traversal such as inorder, preorder etc, in case of a general tree we can do a breadth first traversal from left most to right most child of a node and if that is same then the two trees are identical.

Mirror Tree
Change a tree so that the roles of the left and right pointers are swapped at every node.
So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1

void mirror(struct tree* root)

{

  if (root==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(root->left);

    mirror(root->right);

    temp        = root->left;

    root->left  = root->right;

    root->right = temp;

  }

}

Time Complexity:O(n)
Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Fold-able Tree:

Given a binary tree,find whether it can be foldable or not :

A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Method 1:Without Mirroring
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




Code:

bool IsFoldable(struct node *root)

{

     if (root == NULL)

     {  return true;  }

     return IsFoldableUtil(root->left, root->right);

}

bool IsFoldableUtil(struct node *n1, struct node *n2)

{

    if (n1 == NULL && n2 == NULL)

    {  return true;  }

    if (n1 == NULL || n2 == NULL)

    {  return false; }

    return IsFoldableUtil(n1->left, n2->right) &&

           IsFoldableUtil(n1->right, n2->left);

}

Method 2:Mirroring Tree

1) If tree is empty, then return true.
2) Convert the left subtree to its mirror image
    mirror(root->left);
3) 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 */
4) Revert the changes made in step (2) to get the original tree.
    mirror(root->left);
5) Return result res stored in step 2.

Code:

bool isFoldable(struct node *root)

{

  bool res;

  if(root == NULL)

    return true;

  mirror(root->left);

  res = isStructSame(root->left, root->right);

  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;

}

void mirror(struct node* node)

{

  if (node==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(node->left);

    mirror(node->right);

    temp        = node->left;

    node->left  = node->right;

    node->right = temp;

  }

}

Time complexity: O(n)

Sum Tree:
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
http://www.geeksforgeeks.org/convert-a-given-tree-to-sum-tree/
http://www.geeksforgeeks.org/check-for-children-sum-property-in-a-binary-tree/
http://www.geeksforgeeks.org/convert-an-arbitrary-binary-tree-to-a-tree-that-holds-children-sum-property/
http://www.geeksforgeeks.org/transform-bst-sum-tree/

Double Tree:
For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.
So the tree...
    2
   / \
  1   3

 is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1
Concept:
Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child.
Code:

void doubleTree(struct node* node)

{

  struct node* oldLeft;

  if (node==NULL) return;

  doubleTree(node->left);

  doubleTree(node->right);

  oldLeft = node->left;

  node->left = newNode(node->data);

  node->left->left = oldLeft;

}
Time Complexity: O(n) where n is the number of nodes in the tree.