What is the best approach? Binary Search Tree : Lowest Common Ancestor using only if statements

Question

I have solved the problem with only if statements. It can be solved in various other ways. I have just started programming, so I could not think of using any other data structure for solving this.

My QUESTION :
How to choose the best approach among various ways? And what are the advantages/disadvantages of this best approach compared to my direct naive approach.

Not only for this problem, in general. How to arrive at the possible approach for any problem?

Problem Statement

You are given pointer to the root of the binary search tree and two values v1 and v2. You need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search tree. You only need to complete the function.

My code:

static Node lca(Node root,int v1,int v2)
 { 
    Node r = root;
    if( r == null){
        return null;
    }
    else if(r.data == v1 || r.data == v2){
        return r;
    }
    else if(r.data > v1 && r.data < v2){
        return r;
    }
    else if(r.data > v2 && r.data < v1){
        return r;
    }
    else if( r.data > v1 && r.data > v2){
        lca(r.left, v1, v2);
    }
    else if( r.data < v1 && r.data < v2){
        lca(r.right, v1, v2);
    }
   return null;
 }

Problem link: https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor

Answer 1

Well, here's how I would approach the problem. This relies on the fact that you're dealing with a binary search tree.

For any given node, it can be the LCA if and only if min(v1, v2) is in its left subtree, and max(v1, v2) is in its right subtree. If this isn't true, then the current node clearly can't be an ancestor, because either v1 or v2 cannot be a descendant. Continue traversing down the tree until the LCA condition is met.

Your solution is correct and you have the intuition down, but we can strip out the recursion and simply perform an iterative BST find, which also implicitly contains your if checks.

In terms of advantages, you're really just wasting the implicit recursion call stack space, of which it also has to unwind at the end. Both of our implementations run in O(log N), since you'll examine log N - 1 nodes in the worst case, where v1 and v2 are direct siblings at the bottom of a full and complete tree.

Implementation

1. Swap v1 and v2 if v1 < v2 (remove the need for min and max checks). This implicitly contains both of your if checks for v1 < root < v2 and v2 < root < v1.

2. While the current node's value is smaller than v1 (v1 is in the right subtree) or greater than v2, move towards v1 or v2. This replaces your recursive traversal.

Here's a quick implementation that I checked:

static Node lca(Node root, int v1, int v2)    {
    if (root == null) return null;
    if (v1 > v2) {          
        int temp = v2;
        v2 = v1;
        v1 = temp;
    }
    while (root.data < v1 || root.data > v2) {
        if (root.data < v1)      root = root.right;
        else if (root.data > v2) root = root.left;
    }       
    return root;
}

Answer 2

Better approaches are normally have:

1. Better time or/and space complexity.

2. Readable code.

3. Manages edge cases better.

4. I believe that it will produce smaller code most of the times.

If we look at your code :

 static Node lca(Node root,int v1,int v2)
 { 
     Node r = root;
    if( r == null){
       return null;
    }
    else if(r.data == v1 || r.data == v2){
       return r;
    }
    else if(r.data > v1 && r.data < v2){
       return r;
    }
    else if(r.data > v2 && r.data < v1){
      return r;
    }
    else if( r.data > v1 && r.data > v2){
       lca(r.left, v1, v2);
    }
    else if( r.data < v1 && r.data < v2){
      lca(r.right, v1, v2);
    }
    return null;
 }

Time or Space complexity wise your code is also efficient, I want to touch few point on readability.

1. All your if statements return something, so actually don't need to write else if, just if will be enough.

2. when root is null or v1 or v2, you are returning root only, so you can combine first two conditions.

   NOTE: If you are worried about your elements not present in the tree, you can always check for their existence before call this function. I like it this way, you might want to add your other extra conditions and return null if you want to.

    static Node lca(Node root,int v1,int v2)
    { 
       Node r = root;
      if( r == null || r == v1 || r == v2){
          return root;
      }
   
     if( r.data > v1 && r.data > v2){
         lca(r.left, v1, v2);
     }
   
     if( r.data < v1 && r.data < v2){
         lca(r.right, v1, v2);
     }
     return root; // instead of checking the other two conditions, you can directly return the root.
   }