CODEWITHSUNDEEP
javaalgorithmbinary-treebig-oleast-common-ancestor
brain storm
brain storm

Reputation: 31252

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

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

Upvotes: 1

Views: 3311

Answers (2)

Miljen Mikic
Miljen Mikic

Reputation: 15241

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.

Upvotes: 2

Mihai238
Mihai238

Reputation: 1137

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.

Upvotes: 0

Related Questions