I am not clear if the code tells the algo.
The moment we are calling t.getRoot() implies that we are using parent
pointer. Maybe, i am not a JAVA guy so donot understand how parent is
obtained in this..may be insert times... can someone elaborate..
public Stack<Node> trace(Tree t, Node node){
mainStack = new Stack<Node>();
trace(t.getRoot(),node);
return mainStack;
}
private boolean trace(Node parent, Node node){
mainStack.push(parent);
if(node.equals(parent)){
return true;
}
if(parent.left != null){
if (trace(parent.left, node))
return true;
}
if(parent.right!=null){
if (trace(parent.right, node))
return true;
}
mainStack.pop();
return false;
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Jan 31, 2011 at 9:00 AM, Ashish Goel <[email protected]> wrote:
> I am completely confused here
>
> As i understand, a binary tree has a root, and unrooted binary tree, i
> could not understand what it is and what is the relevance(are we alking
> about forest here?)
>
> Also, i finding LCA for a BST is extremly easy, but for Binary tree, need
> to understand how is it done with an example, request someone to throw some
> light
>
>
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Wed, Jan 12, 2011 at 2:18 AM, saurabh gupta <[email protected]> wrote:
>
>> Based on various comments I think folks do not consider B in the path from
>> A to C which leads to the LCA solution.
>> @SVIX, one can implement the tree with a parent pointer in each node but
>> that doesn't matter in the general case.
>> What you are essentially saying is: consider the tree to be a directed
>> graph with parent -> child link to be one way, if that were the case we
>> cannot even
>> reach from A to C so that is out of question that's why we consider it to
>> be a both way link.
>> Now given this one can always argue that B lies in the path from A to C!
>> i.e. A->D->M->B->M->C
>> so here we can, perhaps, define a shortest path from A to C and it has to
>> go through LCA.
>>
>> @all
>> guys, one request please use @XYZ in case you are referring to a
>> particular post by the person XYZ unless it is a general comment.
>> just to avoid confusion.
>>
>>
>>
>>
>> On Tue, Jan 11, 2011 at 8:06 PM, juver++ <[email protected]> wrote:
>>
>>> The tree can be unrooted. Although, in any tree there is unique path from
>>> one node to another. Not only from the parent to childs.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
>> Says he feels all alone in a threatening world where what lies ahead is
>> vague and uncertain. Doctor says "Treatment is simple. Great clown
>> Pagliacci is in town tonight. Go and see him. That should pick you up."
>> Man
>> bursts into tears. Says "But, doctor...I am Pagliacci."
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
