Clever Geek Handbook

What's the best approach? Binary search tree: lowest common ancestor using only if statements

I only solved the problem with operators. It can be solved in different ways. I just started programming, so I couldn't think of any other data structure to solve this problem.

My question is:
How do you choose the best approach between different ways? And what are the advantages / disadvantages of this best approach versus my direct naive approach.

Not only for this problem, in general. How do you come up with a possible approach to any problem?

Problem Statement

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

enter image description here

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

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

+3


source to share


2 answers


Ok, here's how I would approach the problem. It depends on what you are dealing with with a binary search tree.

For any given node, it can be LCA if and only if it min(v1, v2)

is in the left subtree, but max(v1, v2)

is in its right subtree. If it is not, then the current node clearly cannot be an ancestor, because either v1 or v2 cannot be descendants. Continue walking through the tree until the LCA condition is met.

Your solution is correct and you have your intuition, but we can eliminate recursion and just do an iterative search for the BST, which also implicitly contains your checks if

.

In terms of benefits, you really just waste the stack space of the implicit recursive call from which it should relax at the end as well. Both of our implementations are executed in O(log N)

, since you will consider the log N - 1

worst-case nodes , where v1

they v2

are direct siblings at the bottom of the full and complete tree.



Implementation

  • Translate v1

    and v2

    , if v1 < v2

    (remove the need to check min

    and max

    ). This implicitly contains both of your checks if

    for v1 < root < v2

    and v2 < root < v1

    .

  • As long as the current node value is less than v1

    ( v1

    in the right subtree) or greater than v2

    , go to v1

    or v2

    . This replaces your recursive traversal.

Here is a quick implementation that I tested:

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


source


The best approaches usually have:

  • Best timing and / or space complexity.

  • Readable code.

  • Better controls ribs cases.

  • I believe it will generate less code most of the time.

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

Complexity of time or space, since your code is efficient as well, I want to touch on a few points in terms of readability.

  • All of your operators if

    return something, so you don't really need to write else if

    , just if

    enough.

  • when root

    equals null

    or v1

    or v2

    , you only return root

    , so you can combine the first two conditions.

    NOTE. If you are worried that your elements are not present in the tree, you can always check for their existence before calling this function. I like it, you can add other additional terms and conditions return null

    if you like.

     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.
}
+1


source






More articles:


All Articles