#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
 
struct TreeNode
{
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};
 
typedef struct TreeNode TreeNode;
 
TreeNode* createNode(int data)
{
    TreeNode* temp = (TreeNode *)malloc(sizeof(TreeNode));
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
void printTree(TreeNode* root, int space)
{
    if (root == NULL)
        return;
 
    // Increase distance between levels
    int COUNT = 5;
    space += COUNT;
 
    // Print right child first
    printTree(root->right, space);
 
    // Print current node after space count
    printf("\n");
    for (int i = COUNT; i < space; i++)
        printf(" ");
    printf("%d\n", root->data);
 
    // Print left child
    printTree(root->left, space);
}
 
 
void preorder(TreeNode* root)
{
    if(root==NULL) return;
 
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}
 
 
void inorder(TreeNode* root)
{
    if(root==NULL) return;
 
    inorder(root->left);
 
    printf("%d ", root->data);
 
    inorder(root->right);
}
 
void postorder(TreeNode* root)
{
    if(root==NULL) return;
 
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}
 
int height(TreeNode* root)
{
    if(root==NULL) /// root NULL
    {
        return 0;
    }
    else if(root->left==NULL && root->right==NULL) /// child count: 0
    {
        return 0;
    }
    else
    {
        if(root->left!=NULL && root->right!=NULL) /// child count: 2
        {
            int left_side_height = height(root->left);
            int right_side_height = height(root->right);
 
            if(left_side_height>right_side_height)
            {
                return left_side_height + 1;
            }
            else
                return right_side_height + 1;
 
        }
        else if(root->left!=NULL) /// child count: 1 (Left Child)
        {
            int left_side_height = height(root->left);
            return left_side_height + 1;
        }
        else /// child count: 1 (Right Child)
        {
            int right_side_height = height(root->right);
            return right_side_height + 1;
        }
    }
}
 
 
int findValue(TreeNode* root, int value)
{
    if(root==NULL) return 0;
    else if(root->data==value) return 1;
    else
    {
        int left_answer = findValue(root->left, value);
        int right_answer = findValue(root->right, value);
 
        return left_answer || right_answer;
    }
}
 
int countNodes(TreeNode* root)
{
    if(root==NULL) return 0;
    else
    {
        int left_answer = countNodes(root->left);
        int right_answer = countNodes(root->right);
        return left_answer + right_answer + 1;
    }
}
 
int countLeaves(TreeNode* root)
{
    if(root==NULL) return 0;
    else if(root->left==NULL && root->right==NULL) return 1;
    else
    {
        int left_answer = countLeaves(root->left);
        int right_answer = countLeaves(root->right);
        return left_answer + right_answer;
    }
}
 
int max2(int a, int b)
{
    return a > b ? a : b;
}
 
int max3(int a, int b, int c)
{
    return max2(max2(a,b),c);
}
 
int findMaxValue(TreeNode *root)
{
    if(root==NULL)
    {
        return INT_MIN;
    }
    else
    {
        int left_maximum = findMaxValue(root->left);
        int right_maximum = findMaxValue(root->right);
        int final_maximum = max3(left_maximum, right_maximum, root->data);
        return final_maximum;
    }
}
 
TreeNode* mirrorTree(TreeNode *root)
{
    if(root==NULL)
    {
        return root;
    }
    else
    {
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
 
        root->left = mirrorTree(root->left);
        root->right = mirrorTree(root->right);
        return root;
    }
}
 
int sumInternalValues(TreeNode* root)
{
    if(root==NULL)
        return 0;
    else if(root->left!=NULL || root->right!=NULL)
    {
        return root->data + sumInternalValues(root->left) + sumInternalValues(root->right);
    }
    else
    {
        return 0;
    }
}
 
 
int main()
{
    TreeNode* root = createNode(10);
 
    root->left = createNode(20);
    root->right = createNode(30);
 
    root->left->left = createNode(40);
    root->left->right = createNode(50);
 
    root->right->left = createNode(60);
    root->right->right = createNode(70);
 
    root->right->right->left = createNode(80);
 
	printf("Tree:\n");
    printTree(root, 0);
 
    printf("\n");
 
    root = mirrorTree(root);
 
    printf("Tree:\n");
    printTree(root, 0);
 
    printf("\n");
 
 
    printf("%d\n", sumInternalValues(root));
 
    return 0;
}
 

I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CiNpbmNsdWRlPGxpbWl0cy5oPgoKc3RydWN0IFRyZWVOb2RlCnsKICAgIGludCBkYXRhOwogICAgc3RydWN0IFRyZWVOb2RlKiBsZWZ0OwogICAgc3RydWN0IFRyZWVOb2RlKiByaWdodDsKfTsKCnR5cGVkZWYgc3RydWN0IFRyZWVOb2RlIFRyZWVOb2RlOwoKVHJlZU5vZGUqIGNyZWF0ZU5vZGUoaW50IGRhdGEpCnsKICAgIFRyZWVOb2RlKiB0ZW1wID0gKFRyZWVOb2RlICopbWFsbG9jKHNpemVvZihUcmVlTm9kZSkpOwogICAgdGVtcC0+ZGF0YSA9IGRhdGE7CiAgICB0ZW1wLT5sZWZ0ID0gdGVtcC0+cmlnaHQgPSBOVUxMOwogICAgcmV0dXJuIHRlbXA7Cn0KCnZvaWQgcHJpbnRUcmVlKFRyZWVOb2RlKiByb290LCBpbnQgc3BhY2UpCnsKICAgIGlmIChyb290ID09IE5VTEwpCiAgICAgICAgcmV0dXJuOwoKICAgIC8vIEluY3JlYXNlIGRpc3RhbmNlIGJldHdlZW4gbGV2ZWxzCiAgICBpbnQgQ09VTlQgPSA1OwogICAgc3BhY2UgKz0gQ09VTlQ7CgogICAgLy8gUHJpbnQgcmlnaHQgY2hpbGQgZmlyc3QKICAgIHByaW50VHJlZShyb290LT5yaWdodCwgc3BhY2UpOwoKICAgIC8vIFByaW50IGN1cnJlbnQgbm9kZSBhZnRlciBzcGFjZSBjb3VudAogICAgcHJpbnRmKCJcbiIpOwogICAgZm9yIChpbnQgaSA9IENPVU5UOyBpIDwgc3BhY2U7IGkrKykKICAgICAgICBwcmludGYoIiAiKTsKICAgIHByaW50ZigiJWRcbiIsIHJvb3QtPmRhdGEpOwoKICAgIC8vIFByaW50IGxlZnQgY2hpbGQKICAgIHByaW50VHJlZShyb290LT5sZWZ0LCBzcGFjZSk7Cn0KCgp2b2lkIHByZW9yZGVyKFRyZWVOb2RlKiByb290KQp7CiAgICBpZihyb290PT1OVUxMKSByZXR1cm47CgogICAgcHJpbnRmKCIlZCAiLCByb290LT5kYXRhKTsKICAgIHByZW9yZGVyKHJvb3QtPmxlZnQpOwogICAgcHJlb3JkZXIocm9vdC0+cmlnaHQpOwp9CgoKdm9pZCBpbm9yZGVyKFRyZWVOb2RlKiByb290KQp7CiAgICBpZihyb290PT1OVUxMKSByZXR1cm47CgogICAgaW5vcmRlcihyb290LT5sZWZ0KTsKCiAgICBwcmludGYoIiVkICIsIHJvb3QtPmRhdGEpOwoKICAgIGlub3JkZXIocm9vdC0+cmlnaHQpOwp9Cgp2b2lkIHBvc3RvcmRlcihUcmVlTm9kZSogcm9vdCkKewogICAgaWYocm9vdD09TlVMTCkgcmV0dXJuOwoKICAgIHBvc3RvcmRlcihyb290LT5sZWZ0KTsKICAgIHBvc3RvcmRlcihyb290LT5yaWdodCk7CiAgICBwcmludGYoIiVkICIsIHJvb3QtPmRhdGEpOwp9CgppbnQgaGVpZ2h0KFRyZWVOb2RlKiByb290KQp7CiAgICBpZihyb290PT1OVUxMKSAvLy8gcm9vdCBOVUxMCiAgICB7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CiAgICBlbHNlIGlmKHJvb3QtPmxlZnQ9PU5VTEwgJiYgcm9vdC0+cmlnaHQ9PU5VTEwpIC8vLyBjaGlsZCBjb3VudDogMAogICAgewogICAgICAgIHJldHVybiAwOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGlmKHJvb3QtPmxlZnQhPU5VTEwgJiYgcm9vdC0+cmlnaHQhPU5VTEwpIC8vLyBjaGlsZCBjb3VudDogMgogICAgICAgIHsKICAgICAgICAgICAgaW50IGxlZnRfc2lkZV9oZWlnaHQgPSBoZWlnaHQocm9vdC0+bGVmdCk7CiAgICAgICAgICAgIGludCByaWdodF9zaWRlX2hlaWdodCA9IGhlaWdodChyb290LT5yaWdodCk7CgogICAgICAgICAgICBpZihsZWZ0X3NpZGVfaGVpZ2h0PnJpZ2h0X3NpZGVfaGVpZ2h0KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZXR1cm4gbGVmdF9zaWRlX2hlaWdodCArIDE7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgcmV0dXJuIHJpZ2h0X3NpZGVfaGVpZ2h0ICsgMTsKCiAgICAgICAgfQogICAgICAgIGVsc2UgaWYocm9vdC0+bGVmdCE9TlVMTCkgLy8vIGNoaWxkIGNvdW50OiAxIChMZWZ0IENoaWxkKQogICAgICAgIHsKICAgICAgICAgICAgaW50IGxlZnRfc2lkZV9oZWlnaHQgPSBoZWlnaHQocm9vdC0+bGVmdCk7CiAgICAgICAgICAgIHJldHVybiBsZWZ0X3NpZGVfaGVpZ2h0ICsgMTsKICAgICAgICB9CiAgICAgICAgZWxzZSAvLy8gY2hpbGQgY291bnQ6IDEgKFJpZ2h0IENoaWxkKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHJpZ2h0X3NpZGVfaGVpZ2h0ID0gaGVpZ2h0KHJvb3QtPnJpZ2h0KTsKICAgICAgICAgICAgcmV0dXJuIHJpZ2h0X3NpZGVfaGVpZ2h0ICsgMTsKICAgICAgICB9CiAgICB9Cn0KCgppbnQgZmluZFZhbHVlKFRyZWVOb2RlKiByb290LCBpbnQgdmFsdWUpCnsKICAgIGlmKHJvb3Q9PU5VTEwpIHJldHVybiAwOwogICAgZWxzZSBpZihyb290LT5kYXRhPT12YWx1ZSkgcmV0dXJuIDE7CiAgICBlbHNlCiAgICB7CiAgICAgICAgaW50IGxlZnRfYW5zd2VyID0gZmluZFZhbHVlKHJvb3QtPmxlZnQsIHZhbHVlKTsKICAgICAgICBpbnQgcmlnaHRfYW5zd2VyID0gZmluZFZhbHVlKHJvb3QtPnJpZ2h0LCB2YWx1ZSk7CgogICAgICAgIHJldHVybiBsZWZ0X2Fuc3dlciB8fCByaWdodF9hbnN3ZXI7CiAgICB9Cn0KCmludCBjb3VudE5vZGVzKFRyZWVOb2RlKiByb290KQp7CiAgICBpZihyb290PT1OVUxMKSByZXR1cm4gMDsKICAgIGVsc2UKICAgIHsKICAgICAgICBpbnQgbGVmdF9hbnN3ZXIgPSBjb3VudE5vZGVzKHJvb3QtPmxlZnQpOwogICAgICAgIGludCByaWdodF9hbnN3ZXIgPSBjb3VudE5vZGVzKHJvb3QtPnJpZ2h0KTsKICAgICAgICByZXR1cm4gbGVmdF9hbnN3ZXIgKyByaWdodF9hbnN3ZXIgKyAxOwogICAgfQp9CgppbnQgY291bnRMZWF2ZXMoVHJlZU5vZGUqIHJvb3QpCnsKICAgIGlmKHJvb3Q9PU5VTEwpIHJldHVybiAwOwogICAgZWxzZSBpZihyb290LT5sZWZ0PT1OVUxMICYmIHJvb3QtPnJpZ2h0PT1OVUxMKSByZXR1cm4gMTsKICAgIGVsc2UKICAgIHsKICAgICAgICBpbnQgbGVmdF9hbnN3ZXIgPSBjb3VudExlYXZlcyhyb290LT5sZWZ0KTsKICAgICAgICBpbnQgcmlnaHRfYW5zd2VyID0gY291bnRMZWF2ZXMocm9vdC0+cmlnaHQpOwogICAgICAgIHJldHVybiBsZWZ0X2Fuc3dlciArIHJpZ2h0X2Fuc3dlcjsKICAgIH0KfQoKaW50IG1heDIoaW50IGEsIGludCBiKQp7CiAgICByZXR1cm4gYSA+IGIgPyBhIDogYjsKfQoKaW50IG1heDMoaW50IGEsIGludCBiLCBpbnQgYykKewogICAgcmV0dXJuIG1heDIobWF4MihhLGIpLGMpOwp9CgppbnQgZmluZE1heFZhbHVlKFRyZWVOb2RlICpyb290KQp7CiAgICBpZihyb290PT1OVUxMKQogICAgewogICAgICAgIHJldHVybiBJTlRfTUlOOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGludCBsZWZ0X21heGltdW0gPSBmaW5kTWF4VmFsdWUocm9vdC0+bGVmdCk7CiAgICAgICAgaW50IHJpZ2h0X21heGltdW0gPSBmaW5kTWF4VmFsdWUocm9vdC0+cmlnaHQpOwogICAgICAgIGludCBmaW5hbF9tYXhpbXVtID0gbWF4MyhsZWZ0X21heGltdW0sIHJpZ2h0X21heGltdW0sIHJvb3QtPmRhdGEpOwogICAgICAgIHJldHVybiBmaW5hbF9tYXhpbXVtOwogICAgfQp9CgpUcmVlTm9kZSogbWlycm9yVHJlZShUcmVlTm9kZSAqcm9vdCkKewogICAgaWYocm9vdD09TlVMTCkKICAgIHsKICAgICAgICByZXR1cm4gcm9vdDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBUcmVlTm9kZSogdGVtcCA9IHJvb3QtPmxlZnQ7CiAgICAgICAgcm9vdC0+bGVmdCA9IHJvb3QtPnJpZ2h0OwogICAgICAgIHJvb3QtPnJpZ2h0ID0gdGVtcDsKCiAgICAgICAgcm9vdC0+bGVmdCA9IG1pcnJvclRyZWUocm9vdC0+bGVmdCk7CiAgICAgICAgcm9vdC0+cmlnaHQgPSBtaXJyb3JUcmVlKHJvb3QtPnJpZ2h0KTsKICAgICAgICByZXR1cm4gcm9vdDsKICAgIH0KfQoKaW50IHN1bUludGVybmFsVmFsdWVzKFRyZWVOb2RlKiByb290KQp7CiAgICBpZihyb290PT1OVUxMKQogICAgICAgIHJldHVybiAwOwogICAgZWxzZSBpZihyb290LT5sZWZ0IT1OVUxMIHx8IHJvb3QtPnJpZ2h0IT1OVUxMKQogICAgewogICAgICAgIHJldHVybiByb290LT5kYXRhICsgc3VtSW50ZXJuYWxWYWx1ZXMocm9vdC0+bGVmdCkgKyBzdW1JbnRlcm5hbFZhbHVlcyhyb290LT5yaWdodCk7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9Cn0KCgppbnQgbWFpbigpCnsKICAgIFRyZWVOb2RlKiByb290ID0gY3JlYXRlTm9kZSgxMCk7CgogICAgcm9vdC0+bGVmdCA9IGNyZWF0ZU5vZGUoMjApOwogICAgcm9vdC0+cmlnaHQgPSBjcmVhdGVOb2RlKDMwKTsKCiAgICByb290LT5sZWZ0LT5sZWZ0ID0gY3JlYXRlTm9kZSg0MCk7CiAgICByb290LT5sZWZ0LT5yaWdodCA9IGNyZWF0ZU5vZGUoNTApOwoKICAgIHJvb3QtPnJpZ2h0LT5sZWZ0ID0gY3JlYXRlTm9kZSg2MCk7CiAgICByb290LT5yaWdodC0+cmlnaHQgPSBjcmVhdGVOb2RlKDcwKTsKCiAgICByb290LT5yaWdodC0+cmlnaHQtPmxlZnQgPSBjcmVhdGVOb2RlKDgwKTsKCglwcmludGYoIlRyZWU6XG4iKTsKICAgIHByaW50VHJlZShyb290LCAwKTsKCiAgICBwcmludGYoIlxuIik7CgogICAgcm9vdCA9IG1pcnJvclRyZWUocm9vdCk7CgogICAgcHJpbnRmKCJUcmVlOlxuIik7CiAgICBwcmludFRyZWUocm9vdCwgMCk7CgogICAgcHJpbnRmKCJcbiIpOwoKCiAgICBwcmludGYoIiVkXG4iLCBzdW1JbnRlcm5hbFZhbHVlcyhyb290KSk7CgogICAgcmV0dXJuIDA7Cn0K