Lowest Common Ancestor in Binary Tree(not necessary to be BST)..

Bottom Up Approach:


Explanation :

We traverse the tree only once .. and find out the LCA.Intuition is : 1)First of all we need to traverse the whole tree.Hence any traversing techniue needs to be implemented.[here we are using postorder, because we needs to make decesion based on values calculated.]
    So we added :
        LCA(root.left,p,q);
        LCA(root.right,p,q);
    Now we need certain Inits: if root == null : return null;
            if(root is any of p or q) : return root.
                It means we have reached one of our target node.

2)Decision Block : Since we are returning from bottom to top, after calculations...
    So three cases arises :
        -->Either we found one of our node
        -->Not found one of our node.
        -->Found both nodes
        If we don't find one of our node then  return null;
        But if we found one of our node ... then we need to return that node to its parent.   
        If we found both nodes (then return its root)..Since we are coming from bottom to top, so the first node found having both nodes is our result.


So our code have :

    --> Inits
    --> Traverse Block
    --> Decesion Block. [Why we have written decesion block in last place? Beacuse to make decisions you need to know the values of left subtree and right subtree.]


Ex:

    Let say we have a tree :

        a
        /\                    Let p = f; and q = o       
        b c
        /\ /\
        d e f g
          /\  /
          m n o


For simplicity :
    Lets take a simple tree
        a
        /\
        b c

and p = b, q = c; 
 How our algo proceeds : at A: then goto left subtree and return null||p||q, right subtree and return null||p||q.
    b is returned from leftsubtree and c from right subtree, and root of that will be our LCA


another Example :
        a
        /\            p = d and q = c
        b c
        /\
        d e

    AT A : leftSubtree --> B. then again left subtree... -->D ..return D.
        Now at B... Right sub tree -->At E ...returns null ... since other node is not found.
        So at B value is D.
        Now go to A right subtree .. -->C: return C
        So we have A left Subtree returns D and right subtree returns C..
            SO intuitevely this is the first node, which have p i left subtree and q in right subtree or vice versa.
                          So this is the LCA.

another example :

        a
        /\
        b c                p = m, q= f
        /\ /\
        e f g h
        /\
        m n
   

  We start at A: left subtree -->B -->E -->M since we got M --> so return value to E's left subtree
        E(leftSubtree) = M;
        Now we go to right subtree of E: we found no f ..
        E(right subtree) = null;
        Now non null value is returned to B left subtree value..
        SO B(left subtree) = M.
        Now we calculate B (right subtree)-->We have found 'F'
        So B (right subtree value) = F.
        Hence we return B as LCA   



another example:
        if in previous figure : p=m, q=b
        i.e one node is parent(direct/indirect) of other node ...

        Again as usual, we start at A --> left subtree -->B, now since B is found we return B
            So A(left subtree) = B;[We skipped traversing B childrens]
        Now go to A right subtree -- > we traverse through C and its children an we are unbale to find 'M'--> so it returns null
            So A(right subtree) = M;
        We go to decesion block where we found that non null value should be returned.Hence LCA = B.which is correct.


Time Complexity: Since this algo requires only traversing of tree, So complexity is O(n).
Space Complexity : If tree is balanced then Logn recursive calls and needs to store those on stack.But in worst case it is O(n).




Final Code :

    return : node type
    arguments : root,p,q
    So signature of method : public node LCA(node root, node p, node q)


    Code:

        public node LCA(node root, node p, node q){

        //Inits :
            if(root == null || p == null || q == null)
                return null;
            else if(root == p)
                return p;
            else if(root == q)
                return q;
            else{
                //Traversals
                node L = LCA(root.left,p,q);
                node R = LCA(root.right,p,q)'
                //Decision Code
                if(L != null && R != null)
                    return root; //First node from bottom whose Left and right subtree contains p and q.
                else if(L != null && R== null)
                    return L;
                else if(L == null && R != null)
                    return R;
                else
                    return null;
            }
               
        }