We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Data Structures
  3. Trees
  4. Binary Search Tree : Lowest Common Ancestor
  5. Discussions

Binary Search Tree : Lowest Common Ancestor

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 669 Discussions, By:

votes

Please Login in order to post a comment

  • RubenzZzZ
    7 years ago+ 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;
    }
    
    329|
    Permalink
    View more Comments..
  • yashnisar
    5 years ago+ 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.

    194|
    Permalink
    View more Comments..
  • silentkevie
    4 years ago+ 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?

    157|
    Permalink
  • newsbeidl
    5 years ago+ 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.

    38|
    Permalink
    View more Comments..
  • RodneyShag
    5 years ago+ 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.

    29|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature