C++ O(n) Backtracking + Iterative Easy solution with comments, using 2 stacks, Suggestions welcome :)

#1

The problem assumes that no duplicates are present. Thus a stack of integer(for node val) is used. However, if duplicates are present, simply use stack of TreeNode* and make the changes correspondingly, should not be much difficult

``````// A function that returns false if node with val x does not exist
// Else, returns the path from root to x in stack s
bool hasPath(TreeNode *root, stack<int> &s, int x)
{
if(!root)
{
return false;
}
// Push this node val into stack
s.push(root -> val);

// Is it our required value?
if(root -> val == x)
{
return true;
}

// Check if either of the path is available
if(hasPath(root -> left, s, x) or hasPath(root -> right, s, x))
{
return true;
}

// This path doesn't have x, pop() the topmost element
s.pop();
return false;
}

int Solution::lca(TreeNode* root, int A, int B)
{
// Since there a no duplicates, then storing integers should suffice
stack<int> pathA, pathB;

// Find path to A and B(if they exist)
if(not(hasPath(root, pathA, A) and hasPath(root, pathB, B)))
{
return -1;
}

// Check which one of them has greater path length
// And while popping, check for other val
while(pathA.size() > pathB.size())
{
// Check if A is in B's subtree
if(pathA.top() == B)
{
return B;
}
pathA.pop();
}
while(pathB.size() > pathA.size())
{
// Check if B is in A's subtree
if(pathB.top() == A)
{
return A;
}
pathB.pop();
}

// Here? means we reach a case where both of them have equal path lengths
// That is, both nodes are in different branches
// Now keep pooping from both paths until a common node val is obtained
while(pathA.top() != pathB.top())
{
pathA.pop();
pathB.pop();
}

// Return either of the stack tops
return pathA.top();
}
``````