Get ancestor for lineage tree


  • 0
    S

    Imagine you have a lineage tree that tells for a given person what are his parents.
    For example:

    • A's parents are B and C
    • B's only known parent is D
    • We don't have information about E's parent
    +----->B+------>D
    |
    +
    A
    +      +------->E
    |      +
    +----->C
           +
           +------->F
           +------->I
           +
           G
           +
           +------->J
                    +
                    +------>
           H        +------>L
           +        +
           +------->K
    

    c1) Write a program to determine if two elements have an ancestor in common.
    Some examples:
    F(A,H) = false
    F(G,H) = true
    F(G,C) = false
    3.2) Follow up: Change it now to return the node in common
    3.3) Follow up: Change it to return the distance to the ancestor also


  • 0

    @seulunga can you exampain why F(A,H) = False , they will have some common ancestor if this is lineage tree.
    Also why F(G,H) is True? parents of G are I and J and parent of H are K and unknown.
    Can you provide a better definiton what is common ancestor in this case?
    Thank you


  • 0
    S

    For #1:
    A and H have no ancestor in common.

    A->C->[E,F]
    A->B->D

    H->K->L

    For #2:
    G->J->L
    H->K->L

    Makes sense?


  • 1
    K

    Solution Approach:
    First get all the ancestors of one of the nodes (a) in a hashSet then iterate level by level on the second node (b) at each step checking if the current ancestor of (b) is also an ancestor of (a) by checking the hashSet.

    O(N) time.
    O(N) space

    Note: I don't understand the third modification what is the distance and from which person it is measured person a, person b ?

    Thanks appreciate it!

    public class Person {
    	String key;
    	Person mom, dad;
    
    	public Person(String key) {
    		this.key = key;
    		this.mom = this.dad = null;
    	}
    
    	@Override
    	public String toString() {
    		return "(" + key + ")";
    	}
    }
    
    public class LineageTree {
    
    	public static void main(String[] args) {
    		Person a = new Person("A");
    		Person b = new Person("B");
    		Person c = new Person("C");
    		Person d = new Person("D");
    		Person e = new Person("E");
    		Person f = new Person("F");
    		Person g = new Person("G");
    		Person h = new Person("H");
    		Person i = new Person("I");
    		Person j = new Person("J");
    		Person k = new Person("K");
    		Person l = new Person("L");
    
    		a.mom = c;
    		a.dad = b;
    
    		b.mom = d;
    		c.mom = e;
    		c.dad = f;
    
    		g.mom = i;
    		g.dad = j;
    
    		h.mom = k;
    		k.mom = l;
    		j.mom = l;
    
    		System.out.println(getCommonAncesstor(a, h));
    		System.out.println(getCommonAncesstor(g, h));
    		System.out.println(getCommonAncesstor(g, c));
    	}
    
    	public static boolean hasCommonAncesstor(Person a, Person b) {
    		if (a == null || b == null)
    			return false;
    		return commonAncesstor(a, b) != null;
    	}
    
    	public static Person getCommonAncesstor(Person a, Person b) {
    		if (a == null || b == null)
    			return null;
    		return commonAncesstor(a, b);
    	}
    
    	private static Person commonAncesstor(Person a, Person b) {
    		Set<Person> anodes = new HashSet<Person>();
    		Queue<Person> q = new LinkedList<Person>();
    		q.add(a);
    		while (!q.isEmpty()) {
    			Person cur = q.poll();
    			anodes.add(cur);
    			if (cur.mom != null)
    				q.add(cur.mom);
    			if (cur.dad != null)
    				q.add(cur.dad);
    		}
    
    		int dist = 0;
    
    		q.add(b);
    		while (!q.isEmpty()) {
    			for (int sz = q.size(); sz > 0; sz--) {
    				Person cur = q.poll();
    				if (anodes.contains(cur))
    					return cur;
    				if (cur.mom != null)
    					q.add(cur.mom);
    				if (cur.dad != null)
    					q.add(cur.dad);
    			}
    			dist++;
    		}
    		return null;
    	}
    
    }

  • 0
    Z
    
    	 class Person {
    	 	List<Person> parents;
    	 }
    	 
    	 Perosn findCommonAncestor(Person a, Person b) {
    	 	//Use recursion
    		if(a.equals(b)) {
    			return a;
    		} else {
    			for(Person aP : a.parents) {
    				Person res = findCommonAncestor(aP, b);
    				if(res != null) {
    					return res;
    				}
    			}
    
    			for(Person bP : b.parents) {
    				Person res = findCommonAncestor(a, bP);
    				if(res != null) {
    					return res;
    				}
    			}
    		}
    		return null;
    	 }
    	 
    	 //BFS
    	 Person findCommonAncestor(Person a, Person b) {
    	 	LinkedList<Person> aQ = new LinkedList<Person>();
    	 	LinkedList<Person> bQ = new LinkedList<Person>();
    		HashSet<Person> aSet = new HashSet<Person>();
    		HashSet<Person> bSet = new HashSet<Person>();
    		aQ.add(a);
    		bQ.add(b);
    	 	while(aQ.size() > 0 || bQ.size() > 0) {
    			if(aQ.size() > 0) {
    				LinkedList<Person> aQNext = new LinkedList<Person>();
    				for(Person i : aQ) {
    					if(bSet.contains(i)) {
    						return i;
    					}
    					aSet.add(i);
    					for(Person aP : i.parents) {
    						aQNext.add(aP);
    					}
    				}
    				aQ = aQNext;
    			}
    			
    			if(bQ.size() > 0) {
    				LinkedList<Person> bQNext = new LinkedList<Person>();
    				for(Person i : bQ) {
    					if(aSet.contains(i)) {
    						return i;
    					}
    					bSet.add(i);
    					for(Person bP : i.parents) {
    						bQNext.add(bP);
    					}
    				}
    				bQ = bQNext;
    			}
    		}
    		return null;
    	 }
    

  • 0
    S

    So this is a DAG right? I'm thinking topological sorting might work here.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.