Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 12 of 12

Thread: Lowest Common Ancestor in Binary Tree

  1. #1
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Lowest Common Ancestor in Binary Tree

    Following is my implementation of lowest common ancestor for a Binary Search tree. I have two question:

    1) The time complexity is O(n) and space complexity is O(n) worse case but O(logn) average case for both time and space if BST is balanced. is that correct?
    2) How can i extend my solution to binary trees and not just binary search trees.

    Hope to hear from you soon.
        //The function findOrQueue is to enqueue all elements upto target node to a queue
        public void findOrQueue(Node target, Node top, LLQueue q) {
            int cmp = target.getData().compareTo(top.getData()); 
            if(cmp == 0) {
                q.enqueue(top);
                return ;
            }
            else if (cmp < 0) {
                q.enqueue(top);
                findOrQueue(target, top.getLeftChild(),q);
            }
            else {
                q.enqueue(top);
                findOrQueue(target, top.getRightChild(),q);
           }
        }
     
        public Node LCA(Node n1, Node n2) throws QueueEmptyException {
            LLQueue q1 = new LLQueue();
            LLQueue q2 = new LLQueue();
            findOrQueue(n1,getRoot(),q1);
            findOrQueue(n2,getRoot(),q2);
            Node t = null;
            while (!q1.isEmpty() && !q2.isEmpty()) {
                Node t1 = (Node)q1.dequeue();
                Node t2 = (Node)q2.dequeue();
                if(t1.getData() != t2.getData()) {
                    return t;
                }
                else t = t1;
            }
            if(q1.isEmpty() && q2.isEmpty()) 
                return null;
            else
                return t;
            }


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Lowest Common Ancestor in Binary Tree

    1. Sounds right.

    2. Try building your traversal paths bottom-up instead of top-down. Should give the same time complexity, I think.

  3. #3
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Lowest Common Ancestor in Binary Tree

    doesnt bottom-up mean, i will need a parent pointer??

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Lowest Common Ancestor in Binary Tree

    Yes.

    Otherwise, you'd have to do a full tree traversal (either depth-breadth-first or breadth-depth-first)

  5. #5
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Lowest Common Ancestor in Binary Tree

    so lets stay i have a parent pointer, i still have to traverse to the two nodes whose LCA i am calculating...so how will bottom-up help me?? can u plz help me with this?

    --- Update ---

    or are we assuming we already know the location of the the two nodes and that all the values in the nodes are distinct??

  6. #6
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Lowest Common Ancestor in Binary Tree

    The idea is to build the traversal path bottom-up since this way you don't have to do any unnecessary traversals which you would have to do with regular tree searching.

    After you have the ancestry, you flip the order and go top-down as you're currently doing to find the lowest common ancestry.

  7. #7
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Lowest Common Ancestor in Binary Tree

    can u plz give an example of how to do bottom up traversal?? i dont understand how to build traversal bottom-up without knowing where the node is??

  8. #8
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Lowest Common Ancestor in Binary Tree

    Oh, I was assuming you did know where each node was because your algorithm works with nodes.

    Without knowing that you'd have to do some kind of top-down tree traversal to find the node.

  9. #9
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Lowest Common Ancestor in Binary Tree

    ok, so my findOrQueue function does that....it finds the node first and then as it does find it, it adds the others nodes in its path to a queue....which part r u referring to with respect to bottom-up approach??

  10. #10
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Lowest Common Ancestor in Binary Tree

    You're findOrQueue function won't work for a generic tree. That should be the only function you need to change. I was just suggesting using a bottom-up strategy for the findOrQueue function.

  11. #11
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Lowest Common Ancestor in Binary Tree

    ok, i have one question abt bottom-up traversal, do it go uptill leaves and then up to the nodes i am calculating LCA for? and from there i go to the root?

  12. #12
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Lowest Common Ancestor in Binary Tree

    You basically just start at the node n1/n2, then keep adding their parent, until you reach the root.

    n1 -> n1.parent -> n1.parent.parent -> ... -> root

Similar Threads

  1. [SOLVED] flightpaths, finding lowest cost -- lowest amount of crossovers
    By CjStaal in forum Algorithms & Recursion
    Replies: 4
    Last Post: May 8th, 2012, 12:47 AM
  2. need help with binary tree
    By vash0047 in forum Java Theory & Questions
    Replies: 5
    Last Post: July 12th, 2010, 08:23 AM
  3. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  4. Problem with binary tree
    By Exoskeletor in forum Object Oriented Programming
    Replies: 2
    Last Post: January 8th, 2010, 01:03 PM
  5. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM