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.