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 :wink:

// 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();
}