CODEWITHSUNDEEP
javaalgorithmtreelowest-common-ancestor
Giovanni
Giovanni

Reputation: 121

LCA algorithm in java (working with non binary trees)

I have written a very simple tree class using arrays. This class needs to represent data that are linked together but they can have a different number of connections (i.e. one path could have only 3 nodes and another could have 10). Said that, I need to figure out one possible solution for performing LCA using this class with multiple leaf indexes. this is the code that I have written so far: 

public class ArrayTree {

/**
 * Tree structure
 */
private int[] t;

/**
 * The size of this database
 */
private int N;

/**
 * Creates an array tree with the given size
 * 
 * @param n
 *            the size of the array tree
 */
public ArrayTree(int n) {
    N = n;
    t = new int[N];
}

/**
 * add a new node
 */
public void addNode(int id, int parent) {
    validate(parent);
    t[id] = parent;
}


/**
 * Given an id this method will return an iterable object 
 * orderd from root to leaf
 */
public Iterable<Integer> getEntries(int id) {
    validate(id);
    List<Integer> entries = new ArrayList<Integer>();
    while (id > 1) {
        entries.add(id);
        id = t[id];
        if (id == 0) {
            return null;
        }
    }
    // Reorder entries from root to leaf
    Collections.reverse(entries);
    return entries;
}

/**
 * Private method for validating indexes
 * 
 * @param index
 *            the index
 * @throws IndexOutOfBoundsException
 *             if index > N or index < 0
 */
private void validate(int index) {
    if (index >= N) {
        String error = String.format("Index: %d - Size: %d", index, N);
        throw new IndexOutOfBoundsException(error);
    } else if (index < 0) {
        String error = "negative index";
        throw new IndexOutOfBoundsException(error);
    }
}

}

Thanks in advance, Cheers,

Giovanni

Upvotes: 4

Views: 1075

Answers (2)

pseudo_teetotaler
pseudo_teetotaler

Reputation: 1575

You want to find LCA for two leaf nodes ,call them node1 and node2.

  • Call getEntries() for node1
  • Call getEntries() for node2
  • Now traverse both list till the nodes on the both list are same
  • The first node after which the next node in the list differs is the LCA.

This will work with non binary trees.

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59154

The basic LCA algorithm for multiple nodes does this:

  • Get the depth of each node

  • For each node with depth greater than the minimum depth, transition to the parent until all nodes are at the minimum depth

  • while not all nodes are the same, transition each node to its parent

  • When all the nodes converge to a single node, that's the LCA

I can't really provide code for this, since it's not obvious from your code how you recognize the root, which is necessary for finding the depth of a node.

Upvotes: 2

Related Questions