this solution works if parent pointer is given.
1. Start moving up from both the nodes (if two nodes become equal, fine this
is the common ancestor) till you reach the root node and in between count
the number of nodes you covered in their path for both the nodes. Say 7 for
node A and 10 for node
DON's solution will work
On Sep 3, 11:28 am, Abhishek Yadav algowithabhis...@gmail.com wrote:
this solution works if parent pointer is given.
1. Start moving up from both the nodes (if two nodes become equal, fine this
is the common ancestor) till you reach the root node and in between count
it can done in with 2 stack(size/length of the each stack is hieght of the
tree),(stack1,stack2)
num_stack1=find the first element using in order (pushing the ancestor of
the first element) in first stack.
num_stack2=find the second element using in order (pushing the ancestor of
the second
it can done in with 2 stack(size/length of the each stack is hieght of the
tree),(stack1,stack2)
//find the first element using in order
{
stack1[num_stack1++]=(pushing the ancestor of the first element) in first
stack.
}
//find the second element using in order
stack2[num_stack2++]= (pushing the
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.com wrote:
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
For BST it is easy ...it can be find in O(logn) time ..
when ever we find that the direction we are searching for x and y are
different, that node is the common ancestor ...no need to find either x or y
where the nodes are...
what about binary tree ? how do we search an element in binary tree
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a
Check the c language implementation:
node* LeastCommonAncestor(const node* root, const int data1, const int
data2, int* const status){
static node* ans = NULL;
int l_st=0, r_st=0;
if(root==NULL) return;
if(root-left != NULL)
LeastCommonAncestor(root-left, data1, data2, l_st);
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail if
one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 ||
Don solution is perfect.
i double checked it..
On Aug 9, 9:01 pm, Don dondod...@gmail.com wrote:
tree closestSharedAncestor(tree root, tree node1, tree node2, int
result)
{
tree returnValue = 0;
if (root)
{
if (root == node1) result += 1;
if (root == node2) result += 2;
tree closestSharedAncestor(tree root, tree node1, tree node2, int
result)
{
tree returnValue = 0;
if (root)
{
if (root == node1) result += 1;
if (root == node2) result += 2;
int sum = 0;
tree returnLeft = closestSharedAncestor(root-left, node1, node2,
sum);
if
11 matches
Mail list logo
