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;
            }
               
        }
                   
           

Why Suffix Tree and not Prefix Tree.

To find a pattern we need to find sub string in a text.Since Tries can also find sub string, but there is a catch since they find the sub strings with well defined start and end delimiter.
For ex : Suppose I need to search for a word in a text "bull". Then Trie can do it in O(m) time. But let say we need to find pattern such as "l bid be" now it is a sub-string, but it doesn't have a well defined delimiters starting and ending.
So Basically tries doesn't solve our problem for pattern search.It can find string with well defined boundaries, but not sub string with delimiters.Now this has obvious applications in finding some patterns in Human Gnome.
Like :
"ADCNDJCDNCD CNDJCNDNCDXXCAVDA CDNJCDNCD HBADSCD"
Now if I need to find  "CDNCD HBA" then tries can't do this. Since they stores words and not sub strings.
                                  
Therefore we need some other data structures which can do this.

Firstly our requirement is :
a)We need searching like Tries, means searching of sub string should be done in time proportional to the length of the pattern.
b)Instead of storing individual words in a Trie, we can store either Prefixes or Suffixes of the text(not of the words). Since by this way we can catch the patterns (i.e sub strings) other than individual words.

Now why prefixes or suffixes ?
Since to find sub strings, we must require to search in prefixes or suffixes of text. What it really means is ?
First lets look at Sub string definition.
We can define sub string in two ways:
 -->A prefix of some suffix.
 -->A suffix of some prefix.

For ex :
I have some Text as :
 "abcde h"
 Firstly we must find its prefixes :
  "a"
  "ab"
 "abc"
"abcd"
"abcde"
"abcde h"
Now to find a sub string/pattern let say : "de h"
This sub string must be a suffix of some prefix.
Here in our example it is suffix of last prefix.

Similarly for our other definition of sub string :
We calculate suffixes :
 "h"
" h"
"e h"
"de h"
"cde h"
"bcde h"
"abcde h"
Now to find substring "cde ". It must be  prefix of some suffix.
Here in our case it is prefix of suffix "cde h"

So from this we mean : if we store prefixes or suffixes of the text. We can easily search for a sub string (even without delimiters).

So our next step is :
Create a Trie of prefixes or suffixes of text.

Now our next question is Does Trie of prefixes really do our job?

Logically it seems that we don't require Trie of prefixes.
Since our main concern is the starting delimiter of the sub string.Because if we create a prefix tree, from where we should start our search for pattern.Since our Trie of prefixes always starts with prefixes.Now in order to find intermediate sub string like "cde h", we are not able start the Trie traversal from root of the Trie.
  There are two ways to deal with this problem :
 -->Either create a prefix tree and make some techniques to start traversal from bottom-up.Now this seems to be inappropriate , with some complex traversing from bottom to top,while also to make our Data structure to remain as Trie.
-->Or create a Trie of suffixes.
    Now this will solve our problem, because we will get our starting point from the top of the Trie and match till our sub string length.

So in short we will create a Trie , storing suffixes of entire Text(not individual words).