2
\$\begingroup\$
  1. Input a binary tree (the root node) and 2 other nodes that need to be assessed for finding the least common ancestor (LCA)
  2. Code:
    a. Finding the nodes first with either breadthFirstSearch or depthFirstSearch
    b. If they both exist, find the LCA.
    What searching mechanism would be best here? Using breadthFirst for 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;
    }
    }
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Numeric headings convey no information about the content of those sections. I think all your answers would be much better (and attract more up votes (at least mine)) with meaningful section headers. When I cannot come up with good section headers, I use horizontal rules. I think they look better and less distracting \$\endgroup\$ – janos Jun 29 '16 at 7:08
  • \$\begingroup\$ @janos Done! Thank you for letting me know! \$\endgroup\$ – coderodde Jun 29 '16 at 7:12
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.