Find the first common ancestor of 2 nodes in a binary tree TreeNode* firstCommonAncestor(TreeNode* root, TreeNode* q, TreeNode* p){

if(root == p || root == q){
    return p;
}

if(root == NULL){
    return NULL;
}
TreeNode* temp = firstCommonAncestor(root-&gt;left,q,p);
TreeNode* temp1 = firstCommonAncestor(root-&gt;right,q,p);

if(temp1 != NULL &amp;&amp; temp1 != p){
    return temp1;
}
if(temp != NULL &amp;&amp; temp != p){
    return temp;
}

if((temp == NULL &amp;&amp; temp1 != NULL)||(temp1 == NULL &amp;&amp; temp != NULL)){
    return p;
}

if(temp != NULL &amp;&amp; temp1 != NULL){
    return root;
}


return NULL;

}


I tested this quite thoroughly and it seems to work but looks quite messy. Can anyone give me input on how to improve the style and the performance?
I see some things that may help you improve your code.

Provide complete code

This is really more about getting a good review rather than anything particularly wrong with your code, but as was mentioned in one of the comments, having complete code and a short example definitely helps people both understand your code and shows the intended context.  These are both useful for both clarity and completeness of your question.

Consider a different algorithm

There is a much simpler way to go about this than either the code currently implements or has been suggested by others.  First, consider a post-order traversal.  In a post-order traversal, we visit left nodes, then right nodes, then root nodes.  Consider the following tree:



In it, left nodes are green and right nodes are red.  They are just the names of the months in English (an in-order traversal would display the months in alphabetical order.)  Imagine that we wish to find the first common ancestor of the "February" and "November" nodes.  The algorithm works as follows:


traverse the tree in post-order looking for one of the target nodes
after one of the target nodes is found, keep track of the lowest tree level encountered until the other target node is found
continue the traversal until a node is encountered that is one level above the highest one recorded in step 2.  That node is the first common ancestor.


This requires, at worst case, exactly one traversal of the tree which makes it considerably more efficient that the current algorithm.  In fact, it should be obvious that for an unordered tree, there is no faster algorithm possible.

I've created the following version of a TreeNode structure for this demonstration.

struct TreeNode {
    TreeNode *left;
    TreeNode *right;
    std::string label;
};


The traversal code looks like this:

enum states { LOOKING_FOR_FIRST, LOOKING_FOR_LAST, FINISHING, DONE };

TreeNode *postOrder(TreeNode *n, int depth, TreeNode *t1, TreeNode *t2, states &amp;state)
{
    static int highest;
    static TreeNode *answer;
    if(n != nullptr)
    {
        postOrder(n-&gt;left, depth+1, t1, t2, state);
        postOrder(n-&gt;right, depth+1, t1, t2, state);
        switch (state) {
            case LOOKING_FOR_FIRST:
                if (n == t1 || n == t2) {
                    state = LOOKING_FOR_LAST;
                    highest = depth;
                }
                answer = nullptr;
                break;
            case LOOKING_FOR_LAST:
                highest = std::min(highest, depth);
                if (n == t1 || n == t2) {
                    state = FINISHING;
                    --highest;
                }
                break;
            case FINISHING:
                if (depth == highest) {
                    state = DONE;
                    answer = n;
                }
                break;
            case DONE:
                return answer;
        }
    }
    return answer;
}


The equivalent to your routine could be written like this: 

TreeNode *fca2(TreeNode * root, TreeNode * q, TreeNode * p)
{
    if (root == NULL || q == NULL || p == NULL) {
        return NULL;
    }
    states state = LOOKING_FOR_FIRST;
    return postOrder(root, 0, q, p, state);
}


Now for test code:

testancestor.cpp

#include &lt;iostream&gt;
#include &lt;string&gt;

// code above goes here

int main()
{
    TreeNode tree[]{
        {&amp;tree[1],  &amp;tree[2],  "March"},                //  0
        {&amp;tree[3],  &amp;tree[4],  "January"},              //  1
        {&amp;tree[5],  &amp;tree[6],  "October"},              //  2
        {&amp;tree[7],  &amp;tree[8],  "August"},               //  3
        {&amp;tree[9],  nullptr,   "June"},                 //  4
        {nullptr,   &amp;tree[10], "May"},                  //  5
        {nullptr,   nullptr,   "September"},            //  6
        {nullptr,   nullptr,   "April"},                //  7
        {&amp;tree[11], nullptr,   "February"},             //  8
        {nullptr,   nullptr,   "July"},                 //  9
        {nullptr,   nullptr,   "November"},             // 10
        {nullptr,   nullptr,  "December"},              // 11
    };

    // What is the common node for February and November?
    TreeNode *root = &amp;tree[0];
    TreeNode *a = &amp;tree[8];
    TreeNode *b = &amp;tree[10];
    TreeNode *answer = fca2(root, a, b);
    std::cout &lt;&lt; "common node of " &lt;&lt; a-&gt;label 
              &lt;&lt; " and " &lt;&lt; b-&gt;label &lt;&lt; " is "
              &lt;&lt; answer-&gt;label &lt;&lt; "\n";
    // What is the common node for February and July?
    b = &amp;tree[9];
    answer = fca2(root, a, b);
    std::cout &lt;&lt; "common node of " &lt;&lt; a-&gt;label 
              &lt;&lt; " and " &lt;&lt; b-&gt;label &lt;&lt; " is "
              &lt;&lt; answer-&gt;label &lt;&lt; "\n";
}


Results


common node of February and November is March
common node of February and July is January



Possible enhancements

Note that this test code is not particularly great, but I'm hoping that it's clear enough to demonstrate the basic algorithm.  Improvements could be made.  For example, the code doesn't currently actually stop the traversal when the ancestor node is found, but it certainly could.  Also, the static data would prevent this from being used as-is in a multithreaded environment.  A better alternative would likely be to encapsulate this within a class to avoid both the static variable and the global states.