Find the longest zig-zag path in a binary tree.

Solution #1: The longest zig-zag path is the longest LRLRLR... or RLRLRL... in a tree where 'L' and 'R' stands for left and right children. Also, note that the longest zig-zag path doesn't necessarily starts from the root. Here is the recursive code,

int maxZigzag(struct node* root)
{
    int lcount = 0;
    int rcount = 0;
    int max = 0;
    struct node* temp = root;

    if(root == NULL)
        return 0;

    while(1)
    {
        if(temp->left != NULL)
        {
            lcount++;
            temp = temp->left;
        }
        else
            break;

        if(temp->right != NULL)
        {
            lcount++;
            temp = temp->right;
        }
        else
            break;
    }
    
    while(1)
    {
        if(temp->right != NULL)
        {
            rcount++;
            temp = temp->right;
        }
        else
            break;

        if(temp->left != NULL)
        {
            rcount++;
            temp = temp->left;
        }
        else
            break;
    }

    max = MAX(lcount, rcount);
    max = MAX(max, maxZigzag(root->left));
    max = MAX(max, maxZigzag(root->right));

    return max;
}

int main()
{
    struct node *root;

    insert(&root, 100);
    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 40);
    insert(&root, 30);
    insert(&root, 35);
    insert(&root, 120);
    insert(&root, 110);
    insert(&root, 32);

    printf("maxZigzag = %d\n", maxZigzag(root));
    return 0;
}