Introduction
I noticed that your demo binary tree is not sorted by values, so I assume that we are dealing with the unsorted version of the data structure.
Default values for reference fields
public Treenode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
In Java, the reference fields are initialized with the value null by default. You can simply write
public Treenode(int value) {
this.value = value;
}
Actual algorithms
Your BFS and DFS seem like overkilling it. See Summa summarum for an alternative implementation.
Static vs. non-static
static boolean v1=false,v2=false;
Not good. Consider creating the two variables in the actual LCA routine.
Whitespace
Once again:
static boolean v1=false,v2=false;
You should have a single space before and after each binary operator:
static boolean v1 = false, v2 = false;
Hide the object
Since SearchTree is useless as an object, consider declaring a private constructor.
Summa summarum
All in all, I had this in mind:
Treenode.java:
public class Treenode {
private final int value;
private Treenode right;
private Treenode left;
public Treenode(final int value) {
this.value = value;
}
public int getValue() {
return this.value;
}
public Treenode getLeftChild() {
return this.left;
}
public Treenode getRightChild() {
return this.right;
}
public void setLeftChild(final Treenode child) {
this.left = child;
}
public void setRightChild(final Treenode child) {
this.right = child;
}
@Override
public int hashCode() {
return this.value;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Treenode other = (Treenode) obj;
return this.value == other.value;
}
@Override
public String toString() {
return "[" + this.value + "]";
}
}
SearchTree.java:
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class SearchTree {
private SearchTree() {}
public static Treenode findLeastCommonAncestor(final Treenode root,
final Treenode node1,
final Treenode node2) {
final List<Treenode> list1 = findPath(root, node1);
if (list1 == null) {
return null;
}
final List<Treenode> list2 = findPath(root, node2);
if (list2 == null) {
return null;
}
final Set<Treenode> visitedSet = new HashSet<>(list2);
for (int i = list1.size() - 1; i >= 0; --i) {
final Treenode node = list1.get(i);
if (visitedSet.contains(node)) {
return node;
}
}
return null;
}
private static List<Treenode> findPath(final Treenode root,
final Treenode node) {
final Map<Treenode, Treenode> parentMap = new HashMap<>();
dfs(root, null, parentMap);
if (!parentMap.containsKey(node)) {
return null;
}
final List<Treenode> path = new ArrayList<>();
Treenode current = node;
while (current != null) {
path.add(current);
current = parentMap.get(current);
}
Collections.<Treenode>reverse(path);
return path;
}
private static void dfs(final Treenode currentTreenode,
final Treenode parentTreenode,
final Map<Treenode, Treenode> parents) {
parents.put(currentTreenode, parentTreenode);
if (currentTreenode.getLeftChild() != null) {
dfs(currentTreenode.getLeftChild(), currentTreenode, parents);
}
if (currentTreenode.getRightChild() != null) {
dfs(currentTreenode.getRightChild(), currentTreenode, parents);
}
}
public static void main(String[] args) {
/*
n1 5
/ \ / \
n2 n3 ----> 2 4
/ \ / \
n4 n5 1 3
*/
Treenode n1 = new Treenode(5);
Treenode n2 = new Treenode(2);
Treenode n3 = new Treenode(4);
Treenode n4 = new Treenode(1);
Treenode n5 = new Treenode(3);
Treenode disconnected = new Treenode(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
System.out.println(findLeastCommonAncestor(n1, n4, n3));
System.out.println(findLeastCommonAncestor(n1, n2, disconnected));
}
}
Hope that helps.
