Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    java 8 simplest solution 1. checking if both v1 & v2 less than current node then lca resides in left substree. 2. else if both v1 & v2 greater than current node then lca resides in right substree. 3. if not both previous then lca node is the node where v1 & v2 divide into different subtree or current node data is v1 or v2, so return this node.

    Node node = root;
    while(node != null){
      if(v1 < node.data && v2 < node.data) node = node.left;
      else if(v1 > node.data && v2 > node.data) node = node.right;
      else return node;
    }
    
    return null; // if not found