The Binary Tree here is may not necessarily be a Binary Search Tree.  
The structure could be taken as -

    struct node {
        int data;
        struct node *left;
        struct node *right;
    };

The maximum solution I could work out with a friend was something of this sort -  
Consider [this binary tree](http://lcm.csa.iisc.ernet.in/dsa/node87.html) :

[![Binary Tree][1]][1]

The inorder traversal yields - 8, 4, 9, 2, 5, 1, 6, 3, 7

And the postorder traversal yields - 8, 9, 4, 5, 2, 6, 7, 3, 1

So for instance, if we want to find the common ancestor of nodes 8 and 5, then we make a list of all the nodes which are between 8 and 5 in the inorder tree traversal, which in this case happens to be [4, 9, 2]. Then we check which node in this list appears last in the postorder traversal, which is 2. Hence the common ancestor for 8 and 5 is 2.

The complexity for this algorithm, I believe is O(n) (O(n) for inorder/postorder traversals, the rest of the steps again being O(n) since they are nothing more than simple iterations in arrays). But there is a strong chance that this is wrong. :-)

But this is a very crude approach, and I&#39;m not sure if it breaks down for some case. Is there any other (possibly more optimal) solution to this problem?


  [1]: https://i.stack.imgur.com/Sz5KZ.gif

All Least Common-Ancestor Solutions on Gang of Coders

Total of 1 Least Common-Ancestor Solutions

How to find the lowest common ancestor of two nodes in any binary tree?