what is the time complexity for the LCA in binary tree implemented in Java here

Question

I have this code to find the least common Ancestor of two nodes in binary tree. I think the time complexity is O(log n). but expert opinions are needed. This code works fairly well on my inputs, but I am not sure if I have tested it exhaustively.

here is the code

//LCA of Binary tree
        public static Node LCABT(Node root, int v1, int v2){
            if (root==null)
                return null;
            if (root.data==v1 || root.data==v2){
                return root;
            }
            Node left = LCABT(root.left,v1,v2);
            Node right = LCABT(root.right,v1,v2);

            if(left!=null && right!=null)
                return root;
            else if (left!=null)
                 return left;
            else  return right;
        }

Answer 1

I'm pretty sure this runs in O (n) because you are passing through the whole graph (i.e. at each node you are going in both directions - right and left).

I would suggest reading Tarjan's off-line lowest common ancestors algorithm.

Answer 2

The time complexity of your code is O(n), because you are traversing the whole tree, i.e. you are visiting all its nodes. However, if you don't have BST, but just a binary tree, that is the best you can achieve without having a pointer on a parent node (in that case, build paths from both nodes to root node and return a node that is in both paths). If you have BST, than you can locate both nodes and find least common ancestor in O(h), where h is a height of the tree and that is O(log n) if tree is balanced.

Final remark - if you are preparing for a competition or an interview, make sure to take care of corner cases. Your code does not handle the case where one of nodes is not contained in the tree.