CODEWITHSUNDEEP
algorithmbinary-search-tree
tapananand
tapananand

Reputation: 4852

My Lowest Common Ancestor Algo gives different but logically correct answer than other Algos found online

I was writing a program for finding the Lowest Common Ancestor of a pair of nodes in a Binary Search Tree(given the elements exist in the tree). My Logic was:

  1. Start from root.
  2. If both elems greater than the current element then return root(this is where it differs).
  3. Else if both lesser than root, then recurse on left subtree.
  4. else return root(one is lesser other is greater).

However, Algos found online(http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html) change step 2, in this case they recurse on right subtree and therefore for the following tree:

  2
 / \
1   4
   / \
  3   5

and input 3 and 5, my algo gives 2, while the other algos give 4 as the output.

So, is it me understanding the definition of LCA wrong ('cause 2 is lower than 4 and is a common ancestor) or is my Algo correct.

Upvotes: 0

Views: 94

Answers (1)

Mukul Joshi
Mukul Joshi

Reputation: 324

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. And hence the online version is the correct one which differs from your understanding.

Check out this LCA definition

Also you can avoid recursion if you wish. Just trace the route back to the root node from your candidates. The first common node is the LCA

Upvotes: 1

Related Questions