Problem
- Input a binary tree (the root node) and 2 other nodes that need to be assessed for finding the least common ancestor (LCA)
- Code:
a. Finding the nodes first with eitherbreadthFirstSearchordepthFirstSearch
b. If they both exist, find the LCA.
What searching mechanism would be best here? UsingbreadthFirstfor now.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Treenode {
public int value;
public Treenode right;
public Treenode left;
public Treenode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
public class SearchTree {
static boolean v1=false,v2=false;
public static void main(String[] args) {
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);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
System.out.println("Found BFS? :"+ breadthFirstSearch(n1, 14));
System.out.println("Found DFS? :"+ depthFirstSearch(n1, 5));
System.out.println();
System.out.println("LCA "+" is "+lca(n1,5,50));
}
public static boolean breadthFirstSearch(Treenode root, int value){
if(root==null){
return false;
}
Queue<Treenode> q1 = new LinkedList<Treenode>();
q1.add(root);
while(!q1.isEmpty())
{
Treenode temp = q1.peek();
if(temp!=null) {
q1.remove();
if (temp.value == value) return true;
if (temp.left != null) q1.add(temp.left);
if (temp.right != null) q1.add(temp.right);
}
}
return false;
}
public static boolean depthFirstSearch(Treenode root, int value){
if(root==null){
return false;
}
Stack<Treenode> s1 = new Stack<Treenode>();
s1.add(root);
while(!s1.isEmpty()){
Treenode temp = s1.peek();
if(temp!=null){
s1.pop();
if (temp.value == value) return true;
if (temp.right != null) s1.push(temp.right);
if (temp.left != null) s1.push(temp.left);
}
}
return false;
}
public static Treenode lcaHelper(Treenode head, int x,int y){
if(head==null){
return null;
}
if(head.value == x || head.value ==y){
if (head.value == y){
v2 = true;
return head;
}
else {
v1 = true;
return head;
}
}
Treenode left = lcaHelper(head.left, x, y);
Treenode right = lcaHelper(head.right,x,y);
if(left!=null && right!=null){
return head;
}
return (left!=null) ? left:right;
}
public static int lca(Treenode head, int h1, int h2) {
v1 = breadthFirstSearch(head, h1);
v2 = breadthFirstSearch(head,h2);
if(v1 && v2){
Treenode lca = lcaHelper(head,h1,h2);
return lca.value;
}
return -1;
}
}
Solution
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.
What searching mechanism would be best here?
To answer your main question first: without further information about the structure of the tree and the ordering of nodes and branches, there is no “best” method. With some layouts the breadth first search will give faster result, with others the depth first search will give faster result. There’s not enough information to predict. In the worst case for each method, the entire tree will have to be scanned. Note however that breadth first search will use more memory in deeper trees, so depth first search is a more prudent choice.
Assumptions
It’s important to clarify your assumptions up front, for example:
- The values in the tree are unique
- No node will have the value -1 (all values are positive?)
Testing
One example case run in the main method is insufficient, by far, to verify the logic of such nontrivial program. Consider using proper test techniques, for example JUnit.
Algorithm
I don’t understand your implementation. I don’t think it will work for more complex examples with deeper trees. See the implementation of Coderodde. He created linked lists from the paths to the nodes, and then found the first common element. That’s clear, easy to understand and it will surely work.
An interesting variation on that is not using a set, but iterating over the two lists in parallel, until a different element is found, or the end of either list is reached.
Variable scope
It’s a good practice to declare variables in the smallest necessary scope. Especially it’s recommended to avoid static variables. The static variables v1 and v2 are unnecessary, and should be eliminated.
Naming
The static variables v1 and v2 are poorly named. They don’t mean anything, they don’t help the reader understand their purpose. When you try to come up with a better name for variables, it often happens that you find a logical, design problem. You may have realized then that you don’t really need these variables.
Readability
The indentation is inconsistent and messy throughout. Copy paste the code into any modern IDE and use the auto-reformat feature to fix it. Always do that before asking for a review.
Simplifications
In both search methods you check if peek from a queue or a stack returns null. This is redundant, as the condition is within a while loop that ensures the data structures are not empty, and also you never insert null values. In short, you can safely remove these conditions.