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
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 eleme
DON's solution will work
On Sep 3, 11:28 am, Abhishek Yadav 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
> the number of nodes you
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 B
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
effic
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain 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)
> {
>
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
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 || root.left.
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);
can someone explain in general Don's code?
On Wed, Aug 10, 2011 at 8:54 AM, Venkat wrote:
> Don solution is perfect.
> i double checked it..
>
> On Aug 9, 9:01 pm, Don wrote:
> > tree closestSharedAncestor(tree root, tree node1, tree node2, int
> > &result)
> > {
> > tree returnValue = 0;
Don solution is perfect.
i double checked it..
On Aug 9, 9:01 pm, Don 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;
> int
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 (returnLe
12 matches
Mail list logo