Threaded Binary Tree

Threaded binary tree saves stack recursion space used for traversing a tree , by making traversal iterative istead of recursive.
    The right most null node is made to be ponted to its inorder successor while tree formation .
    So space complexity becomes O(1) from O(N)



#include<cstdio.h>
#include<iostream>


//structure of a node in a threded binary tree
struct treeNode{
    int data;
    struct treeNode* right;
    struct treeNode* left;
    bool isRightHanded;
       
};

struct treeNode* leftMost(struct  treeNode* curr)
{
    if (curr == NULL)
        return NULL;
    while (curr->left != NULL)
        curr = curr->left;
    return curr;

}



void traverseThrededTree(struct treeNode* root)
{
    if (root == NULL)
    {
        printf("Empty tree");
        return ;
    }

    struct treeNode* cur = leftMost(root);

    while (cur != NULL)
    {
        printf("%d", cur->data);

        //if node is right handed , go to next node
        if (cur->isRightHanded)
        {
            cur = cur->right;
        }
        else // else go to next leftmost node of the right node , if it exist
        {
            cur = leftMost(cur->right);
        }
    }




}

Find size of a binary tree

#include<stdio.h>
#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int sizeOfTree(struct treeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    return sizeOfTree(root->left) + 1 + sizeOfTree(root->right);
}

int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Size of the tree is %d", sizeOfTree(root));
    getchar();
    return 0;
}

Print all paths from root to leaf node in a binary tree

Maintain an array path[] having node's data on each level , and the length of path[] , on every  new level oush the node's data to path[] and increment path len.
If we are at the leaf node ,  print the path[] , or try recursing to left and right child 

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen);

void printArray(int ints[], int len)
{
    int i;
    for (i = 0; i<len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}
void mirror(struct treeNode* node)
{
    if (node == NULL)
        return;
    //go to left node
    mirror(node->left);
    mirror(node->right);

    //swap left and right node child pointers
    struct treeNode* temp = node->left;
    node->left = node->right;
    node -> right = temp;


}

void printPaths(struct node* node)
{
    int path[1000];
    printPathsRecur(node, path, 0);
}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen)
{
    if (node == NULL)
    {
        return;
    }
   
    //add the node to path at this level
    pat[pathlen] = node -> data;
    //increment path len
    ++pathlen;

    //if its a leaf node , print the path
    if (node->right == NULL && node->left == NULL)
    {
        printArray(pat, pathlen);
    }
    else
    {
        //try bith subtree
        printPathsRecur(node->left, pat, pathlen);
        printPathsRecur(node->right, pat, pathlen);
    }
}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    /* Print all root-to-leaf paths of the input tree */
    printPaths(root);

    getchar();
    return 0;
   
}

Mirror a Binary tree

Mirror a binary tree works by recursing in post order , and then swapping left and right pointers of the node

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void mirror(struct treeNode* node)
{
    if (node == NULL)
        return;
    //go to left node
    mirror(node->left);
    mirror(node->right);

    //swap left and right node child pointers
    struct treeNode* temp = node->left;
    node->left = node->right;
    node -> right = temp;


}

void inOrder(struct treeNode* node)
{
    if (node == NULL)
        return;

    inOrder(node->left);
    printf("%d ", node->data);

    inOrder(node->right);
}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    /* Print inorder traversal of the input tree */
    printf("\n Inorder traversal of the constructed tree is \n");
    inOrder(root);

    /* Convert tree to its mirror */
    mirror(root);

    /* Print inorder traversal of the mirror tree */
    printf("\n Inorder traversal of the mirror tree is \n");
    inOrder(root);

    getchar();
    return 0;
   
}

Find Height of a Tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int maxDepth(struct treeNode* root)
{
    if (root == NULL)
        return 0;
    else
           
    {   

        return ( max(maxDepth( root->left) , maxDepth(root->right) ) + 1 );
    }
}

int main()
{
    struct treeNode *root = newNode(1);

    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Hight of tree is %d", maxDepth(root));

    getchar();
    return 0;
   
}

Diameter of Binary Tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}


void printArray(int ints[], int len)
{
    int i;
    for (i = 0; i<len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}

int maximum(int a, int b)
{
    return a>=b?a : b;
}

int height(struct treeNode* root)
{
    if (root == 0)
    {
        return 0;
    }

    int h = 1 + maximum(height(root->left) , height(root->right));
    return h;
}

/*
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1
*/

int diameter(struct treeNode* root)
{
    if (root == 0)
        return 0;
    int rHeight = height(root->right);
    int lHeight = height(root->left);

    int lDiameter = diameter(root->left);
    int rDiameter = diameter(root->right);

    return maximum(1 + rHeight + lHeight, maximum(lDiameter, rDiameter));

}




int main()
{
    /* Constructed binary tree is
    1
    /   \
    2      3
    /  \
    4     5
    */
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Diameter of the given binary tree is %d\n", diameter(root));

    getchar();
    return 0;
}

Delete a Binary Tree

Using postorder traversal , delete tree , as we should delete child nodes first instead of parent node for straight tree deletion
#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};   


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void deleteTree(struct treeNode* node)
{
    if (node == NULL)
    {
        return;
    }

    deleteTree(node->left);
    deleteTree(node->right);
    free(node);

}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    deleteTree(root);
    root = NULL;

    printf("\n Tree deleted ");

    getchar();
    return 0;
   
}

Check If Both Binary Trees Are Identical

Complexity O(m) where m is size of tree with nodes m <=n , where n is size of other tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int isIdentical(struct treeNode* A, struct treeNode* B)
{
    //if both are empty , return 1
    if (A == NULL  && B == NULL)
    {
        return 1;
           
    }

    if(A != NULL && B != NULL)
    {
        //check if the data at root or root of subtree (while recursion) , and left and right subtree are equal
        //by recursing to left and right subtree
        return A->data == B->data && isIdentical(A->left, B->left) && isIdentical(A->right, B->right);
    }
    //else both trees are not identical ,one empty and other is not ,  return 0
    else return 0;
}

int main()
{
    struct treeNode *root1 = newNode(1);
    struct treeNode *root2 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(3);
    root1->left->left = newNode(4);
    root1->left->right = newNode(5);

    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);

    if (isIdentical(root1, root2))
        printf("Both tree are identical.");
    else
        printf("Trees are not identical.");

    getchar();
    return 0;
}