Binary Search Tree : Lowest Common Ancestor
Binary Search Tree : Lowest Common Ancestor
+ 68 comments Solution is based on the following thought: The value of a common ancestor has to always be between the two values in question.
static Node lca(Node root,int v1,int v2) { //Decide if you have to call rekursively //Samller than both if(root.data < v1 && root.data < v2){ return lca(root.right,v1,v2); } //Bigger than both if(root.data > v1 && root.data > v2){ return lca(root.left,v1,v2); } //Else solution already found return root; }
+ 7 comments It would be nice if the sample tree given in the example would be a Binary Search Tree. The example could mislead people to solve this problem for a Binary Tree.
+ 2 comments Is there no oversight for questions? There are two ridiculous problems with this one.
1) The first example given is not a BST. So why include it in the problem at all when the statement starts off talking about BSTs?
2) An ancestor, by definition, is something from which another is descended. So it is impossible to be your own ancestor. Therefore Test Case #2 is wrong.
Is the point of HackerRank to solve interesting algorithmic questions or to beat you over the head with useless and/or wrong information?
+ 5 comments As with so many challenges here, this is a terrible problem description. This is one of the worst. The "Lowest common ancestor" is not even defined! And the sole example just returns the root of the tree! Horrible, lazy, horrible problem description. Why doesn't HackerRank have standards on their problems? We should be allowed to VOTE on how well defined a problem is, otherwise we end up with problems like this one.
+ 3 comments Efficient Java solution - passes 100% of test cases
From my HackerRank solutions.
Make sure to leverage the fact that this is a binary search tree. We assume the tree has unique values.
Runtime: O(log n) on a balanced tree
Space Complexity: O(1)I solve it iteratively since recursion would take O(log n) space complexity
static Node lca(Node n, int v1, int v2) { while (n != null) { if (n.data > v1 && n.data > v2) { n = n.left; } else if (n.data < v1 && n.data < v2) { n = n.right; } else { break; } } return n; }
Let me know if you have any questions.
Sort 669 Discussions, By:
Please Login in order to post a comment