// binary.c
// comile with:
//   gcc -o binary binary.c
// and run.

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

typedef struct node node;

struct node
{
    node *_leftChild;
    int _value;
    node *_rightChild;
    node *_parent;
};

node* nn(node *left, int value, node *right)
{
    node *n = (node*)malloc(sizeof(node));
    n->_leftChild = left;
    n->_rightChild = right;
    n->_value = value;
    n->_parent = 0;
    return n;
}

void solidify(node *n)
{
    if(n->_leftChild)
    {
        n->_leftChild->_parent = n;
        solidify(n->_leftChild);
    }
    if(n->_rightChild)
    {
        n->_rightChild->_parent = n;
        solidify(n->_rightChild);
    }
}

void printascsingle(node *n)
{
    int direction = 0; //1 - right down ; 2 - left down ; 3 - right up ; 4 - left up

    while(n->_leftChild)
        n = n->_leftChild;

    while(1)
    {
        if(!n->_parent && direction == 2)
            break;
        else if(direction == 1)
        {
            printf(" %i\n", n->_value);
            if(n->_rightChild)
            {
                n = n->_rightChild;
                direction = 3;
            }
            else
            {
                if(n->_value < n->_parent->_value)
                    direction = 1;
                else
                    direction = 2;
                n = n->_parent;
            }
        }
        else if(direction == 2)
        {
            if(n->_value <= n->_parent->_value)
                direction = 1;
            n = n->_parent;
        }
        else
        {
            if(n->_leftChild)
            {
                n = n->_leftChild;
                direction = 4;
            }
            else
            {
                printf(" %i\n", n->_value);
                if(n->_rightChild)
                {
                    n = n->_rightChild;
                    direction = 3;
                }
                else
                {
                    if(n->_value < n->_parent->_value)
                        direction = 1;
                    else
                        direction = 2;
                    n = n->_parent;
                }
            }
        }
    }
}

void printascdouble(node *n1, node *n2)
{
    int p1direction = 0;
    int p2direction = 0;

    node *p1 = n1;
    node *p2 = n2;

    node *r;
    int rdirection;

    while(p1->_leftChild)
        p1 = p1->_leftChild;
    while(p2->_leftChild)
        p2 = p2->_leftChild;

    while(1)
    {
        if((!p1->_parent && (p1direction == 2 || !p1->_rightChild)) || (!p2->_parent && (p2direction == 2 || !p2->_rightChild)))
            break;

        if(p1->_value <= p2->_value)
        {
            if(p1direction == 1)
            {
                printf(" %i\n", p1->_value);
                if(p1->_rightChild)
                {
                    p1 = p1->_rightChild;
                    p1direction = 3;
                }
                else
                {
                    if(p1->_value < p1->_parent->_value)
                        p1direction = 1;
                    else
                        p1direction = 2;
                    p1 = p1->_parent;
                }
            }
            else if(p1direction == 2)
            {
                if(p1->_value < p1->_parent->_value)
                    p1direction = 1;
                p1 = p1->_parent;
            }
            else
            {
                if(p1->_leftChild)
                {
                    p1 = p1->_leftChild;
                    p1direction = 4;
                }
                else
                {
                    printf(" %i\n", p1->_value);
                    if(p1->_rightChild)
                    {
                        p1 = p1->_rightChild;
                        p1direction = 3;
                    }
                    else
                    {
                        if(p1->_value < p1->_parent->_value)
                            p1direction = 1;
                        else
                            p1direction = 2;
                        p1 = p1->_parent;
                    }
                }
            }
        }
        else
        {
            if(p2direction == 1)
            {
                printf(" %i\n", p2->_value);
                if(p2->_rightChild)
                {
                    p2 = p2->_rightChild;
                    p2direction = 3;
                }
                else
                {
                    if(p2->_value < p2->_parent->_value)
                        p2direction = 1;
                    else
                        p2direction = 2;
                    p2 = p2->_parent;
                }
            }
            else if(p2direction == 2)
            {
                if(p2->_value < p2->_parent->_value)
                    p2direction = 1;
                p2 = p2->_parent;
            }
            else
            {
                if(p2->_leftChild)
                {
                    p2 = p2->_leftChild;
                    p2direction = 4;
                }
                else
                {
                    printf(" %i\n", p2->_value);
                    if(p2->_rightChild)
                    {
                        p2 = p2->_rightChild;
                        p2direction = 3;
                    }
                    else
                    {
                        if(p2->_value < p2->_parent->_value)
                            p2direction = 1;
                        else
                            p2direction = 2;
                        p2 = p2->_parent;
                    }
                }
            }
        }
    }

    if(p1->_parent)
    {
        r = p1;
        rdirection = p1direction;
    }
    else
    {
        r = p2;
        rdirection = p2direction;
    }

    while(1)
    {
        if(!r->_parent && (rdirection == 2 || !r->_rightChild))
            break;
        else if(rdirection == 1)
        {
            printf(" %i\n", r->_value);
            if(r->_rightChild)
            {
                r = r->_rightChild;
                rdirection = 3;
            }
            else
            {
                if(r->_value < r->_parent->_value)
                    rdirection = 1;
                else
                    rdirection = 2;
                r = r->_parent;
            }
        }
        else if(rdirection == 2)
        {
            if(r->_value < r->_parent->_value)
                rdirection = 1;
            r = r->_parent;
        }
        else
        {
            if(r->_leftChild)
            {
                r = r->_leftChild;
                rdirection = 4;
            }
            else
            {
                printf(" %i\n", r->_value);
                if(r->_rightChild)
                {
                    r = r->_rightChild;
                    rdirection = 3;
                }
                else
                {
                    if(r->_value < r->_parent->_value)
                        rdirection = 1;
                    else
                        rdirection = 2;
                    r = r->_parent;
                }
            }
        }
    }
}

int main()
{
    node *tree1 = nn(nn(nn(0,1,0),3,nn(nn(0,4,0),6,nn(0,7,0))),8,nn(0,10,nn(nn(0,13,0),14,0)));
    node *tree2 = nn(nn(nn(0,1,nn(0,2,0)),3,nn(0,12,0)),13,nn(0,14,nn(0,18,0)));

    solidify(tree1);
    solidify(tree2);

    printascsingle(tree1);
    printascsingle(tree2);

    printascdouble(tree1, tree2);

    return 0;
}