Re: [algogeeks] Least Common Ancestor in STL MAP
On 3/21/13 5:02 PM, Avinash wrote: Given a STL map, say mapint, bool m1. Given two value a b that may or may not exists in m1. Find the Least Common Ancestor in STL MAP. Remember you don't have access to root, so you need to iterate using iterator. Use the methods/function of MAP forex begin, end, find etc. Solution should be efficient in terms of time complexity (forex if we use method find, we get it in O(logN) internally) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. STP Map is a sorted associative container. It stores key-value pair, in sorted order. For more information on the above read about map [1] and about sorted associative containers. [2] Map stores key-value pair and use iterators for traversal. The iterators will either give you next value (forward iterator) or previous value (reverse iterator). The container does *NOT* know, how it is implemented underneath the hood. Given that you have the knowledge that map is implemented as Red-Black tree (a form of balance tree) in libstd++ you can not abuse the container to tweak the internals. I can write my own sorted associative container, use whatever data structure I want underneath and release it and it would still be correct. SGI gives specifications. Each compiler is free to implement its own /internal/ implementation. The STL does not expose the internals as it would violate OOP principles, i.e. exposing the underlying data structures as it may lead to undesirable behavior. Think of it like this, say N values are inserted in a map. You don't know where is root, what is the tree structure ? Hell, you don't even know if that is a tree. The point is you are not supposed to know. You basically don't know anything apart from two facts: (a) You can get ``value'' from a given ``key''. (b) You can traverse in sorted or reverse-sorted manner. This /nullifies/ your question. In case you are interested in LCA, create your own Tree structure instead of trying to abuse the de facto sorted associative container of the Standard Template Library. [1] http://www.sgi.com/tech/stl/Map.html [2] http://www.sgi.com/tech/stl/SortedAssociativeContainer.html -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Least Common Ancestor in STL MAP
Given a STL map, say mapint, bool m1. Given two value a b that may or may not exists in m1. Find the Least Common Ancestor in STL MAP. Remember you don't have access to root, so you need to iterate using iterator. Use the methods/function of MAP forex begin, end, find etc. Solution should be efficient in terms of time complexity (forex if we use method find, we get it in O(logN) internally) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Least Common Ancestor in an n ary tree
Find LCA in n ary tree ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Least Common Ancestor in an n ary tree
If there are N nodes and it is an n-ary tree, O(N) pre-processing is required for every node, storing its parent in each step. Subsequently, if LCA(u,v) is to be found, produce the list of ancestors A(u) and A(v), which can be done in O(log-n N) steps. Then compare A(u) and A(v) to find the furthest element in A(u) and A(v) that matches. So O(N) pre-processing and O(log-n N) query time complexity. On Fri, Aug 5, 2011 at 10:22 AM, ankit sambyal ankitsamb...@gmail.com wrote: Find LCA in n ary tree ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Gaurav Menghani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Least Common Ancestor
http://geeksforgeeks.org/?p=1029 follow the link fa one more soln.. //BE COOL// kavi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Least Common Ancestor
Solution in the link is for BST, not for BT On Thu, Jul 28, 2011 at 3:15 PM, kavitha nk kavithan...@gmail.com wrote: http://geeksforgeeks.org/?p=1029 follow the link fa one more soln.. //BE COOL// kavi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Least Common Ancestor
oh 5n sry...how to get practiced wit algo???help me //BE COOL// kavi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Least Common Ancestor
First make an iterative DFS function which stores node pointers on the stack
instead of node values and break as soon as the node value of the node
pointer on the top of the stack reaches a specified value.
void iterative_dfs(Node *root,int n1);
Let n1 and n2 be the values whose LCA is to be found in a binary tree whose
root pointer is : root
Step1 : iterative_dfs(root,n1)
Step2 : int arr1[];
for i=0 to top // top is the index of the top of the
stack
arr1[i]=stack[i]
Step3: iterative_dfs(root,n2)
Step4:int arr2[];
for i=0 to top
arr2[i]=stack[i]
Step5: for i=0 to n
{
if(arr1[i]!=arr2[i])
break;
}
Step6:
return arr1[i-1]-value; // arr1[i-1] or arr2[i-1] contains
the node pointer of least common ancestor
Time : O(n)
Space: O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Least Common Ancestor
@$iva : check this link : http://www.technicalypto.com/search/label/binary%20tree On Wed, Jul 27, 2011 at 11:08 AM, sivaviknesh s sivavikne...@gmail.comwrote: How to find Least Common Ancestor of a BINARY TREE without using PARENT POINTERS ? give algo / ideas plz ?? -- Regards, $iva -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
