Lowest Common Ancestor Time Limit Exceeded using the root to node path approach

Question

I have implemented the solution for LCA problem. The problem statement is that Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The approach that I used, was to find the path from root to the given 2 nodes and store the 2 paths in a vector. Start comparing nodes in both paths starting from root(the path till the LCA should match for both p and q), So the node just before when the mismatch occurs in the paths will be the LCA.

But 29/31 test cases alone passed in Leetcode, Got Time Limit Exceeded for very large inputs. Here is the code :

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> path;
    void pathUntilNode(TreeNode* root, vector<TreeNode*> res, TreeNode* p){
        if(root==NULL) return;
        res.push_back(root);
        if(root==p){
            path=res;
            return ;
        }
        pathUntilNode(root->left, res, p);
        pathUntilNode(root->right, res, p);
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return NULL;
        vector<TreeNode*> res;
        pathUntilNode(root, res, p);
        vector<TreeNode*> path1 = path;
        pathUntilNode(root, res, q);
        vector<TreeNode*> path2 = path;
        int i;
        for(i=0;i<min(path1.size(),path2.size());i++){
            if(path1[i]!=path2[i])
                return path1[i-1];
        }
        return path1[i-1];
    }  
};

The time complexity is O(N) as far as I can see. Don't understand why I'm getting TLE.

Answer 1

The problem is that your code makes all vector pointers to reference the same vector. But you need path1 and path2 to be separate vectors. So if after doing path = res you have another res.push_back(root), this will affect path which has become a synonym for res...

Secondly, your recursive search still continues searching even after a match was found. This is a waste of time. It should exit the recursion tree as soon as possible. So if it comes back from a search in a node's left child -- where it found a match -- it should not continue a search in the node's right child.

There are several ways to solve the first issue, but essentially the two paths must be separate vectors. One way is to make the recursive function return the path if it is found (or an empty one if not). That way the paths will be built in reverse, but that is easy to tackle:

vector<TreeNode*> notfound;

vector<TreeNode*> pathUntilNode(TreeNode* root, TreeNode* p) {
    if (root == NULL) return notfound;
    if (root == p) return { root }; // found: start a new path
    vector<TreeNode*> path = pathUntilNode(root->left, p);
    // only look in the other subtree if no success yet...
    if (path == notfound) path = pathUntilNode(root->right, p);
    if (path != notfound) path.push_back(root);  // success: extend the path
    return path;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode*> path1 = pathUntilNode(root, p);
    vector<TreeNode*> path2 = pathUntilNode(root, q);
    reverse(path1.begin(), path1.end());
    reverse(path2.begin(), path2.end());
    // no change below this point
    int i;
    for (i = 0; i < min(path1.size(), path2.size()); i++) {
        if (path1[i] != path2[i])
            return path1[i-1];
    }
    return path1[i-1];
}