- public PhylogenyNode obtainLCA( final PhylogenyNode node1, final PhylogenyNode node2 ) {
- _temp_hash_set.clear();
- PhylogenyNode n1 = node1;
- PhylogenyNode n2 = node2;
- _temp_hash_set.add( n1.getId() );
- while ( !n1.isRoot() ) {
- n1 = n1.getParent();
- _temp_hash_set.add( n1.getId() );
+ public final static PhylogenyNode calculateLCA( PhylogenyNode node1, PhylogenyNode node2 ) {
+ if ( node1 == node2 ) {
+ return node1;
+ }
+ if ( ( node1.getParent() == node2.getParent() ) ) {
+ return node1.getParent();
+ }
+ int depth1 = node1.calculateDepth();
+ int depth2 = node2.calculateDepth();
+ while ( ( depth1 > -1 ) && ( depth2 > -1 ) ) {
+ if ( depth1 > depth2 ) {
+ node1 = node1.getParent();
+ depth1--;
+ }
+ else if ( depth2 > depth1 ) {
+ node2 = node2.getParent();
+ depth2--;
+ }
+ else {
+ if ( node1 == node2 ) {
+ return node1;
+ }
+ node1 = node1.getParent();
+ node2 = node2.getParent();
+ depth1--;
+ depth2--;
+ }