top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Help me to find least common ancestor in a BST.

+4 votes
46 views

I have tried bruteforce method but it's complexity is of O(n^2) , i am interested in O(n) or O(nlon n)
enter image description here

for the tree given above common ancestor of node 1 and 7 is 4. I am much interested in function not the whole program,function shoud take three argument as root of the tree, node1 and node 2

posted Jun 16, 2016 by Shahsikant Dwivedi

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button

Similar Questions
+7 votes

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm/code for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

+7 votes
                    10
                    /  \                    
                   7     15
                  / \    / \
                 6   8  12  18
                /     \
               5       9
            (Given Binary tree) 
+1 vote

enter image description here

for example in above tree ancestor of 7 is : 7 3 1

+5 votes
      40
      /\
     20 60
     /\  \
   10 30  80
      /   /\
     25  70 90
           \
           75

longest path 
25 30 20 40 60 80 70 75 
Answer
    25 ----> 75
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...