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 [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.
