# Lowest Common Ancestor of a Binary Search Tree Runtime Error

• ``````/**
* 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:
unordered_map <TreeNode*, TreeNode*> parent;
unordered_map <TreeNode*, int> depth;
unordered_map <TreeNode*, unordered_map<int, TreeNode*> > lcaTable;

void bfs(TreeNode* root, TreeNode* p, TreeNode* q) {
queue <TreeNode*> Q;
Q.push(root);
parent[root] = root;
depth[root] = 0;
lcaTable[root][0] = root;
bool foundP = false, foundQ = false;
while(!Q.empty()) {
TreeNode* node = Q.front();
Q.pop();
TreeNode* left = node->left;
TreeNode* right = node->right;
if(left) {
if(left->val == p->val) {
foundP = true;
} else if(left->val == q->val) {
foundQ = true;
}
lcaTable[left][0] = node;
depth[left] = depth[node] + 1;
parent[left] = node;
Q.push(left);
}
if(right) {
if(right->val == p->val) {
foundP = true;
} else if(right->val == q->val) {
foundQ = true;
}
lcaTable[right][0] = node;
depth[right] = depth[node] + 1;
parent[right] = node;
Q.push(right);
}
if(foundP and foundQ) {
break;
}
}
}

void lcaInit(TreeNode* p) {
for(int i = 1; (1 << i) < depth[p]; ++i) {
lcaTable[p][i] = lcaTable[lcaTable[p][i - 1]][i - 1];
}
}

int logDepth(TreeNode* p) {
int log = 1;
while(true) {
int next = log + 1;
if((1 << next) > depth[p]) break;
log++;
}
return log;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root or !p or !q) return nullptr;
bfs(root, p, q);
lcaInit(p);
lcaInit(q);

if(depth[p] < depth[q]) swap(p, q);

int log = logDepth(p);

for(int i = log - 1; i >= 0; --i) {
if(depth[p] - (1 << i) >= depth[q]) {
p = lcaTable[p][i];
}
}

if(p->val == q->val) return p;

log = logDepth(p);
for(int i = log - 1; i >= 0; --i) {
if(lcaTable[p][i] != lcaTable[q][i]) {
p = lcaTable[p][i], q = lcaTable[q][i];
}
}
cout << parent[p] << " " << parent[p]->val << endl; // for debug purpose
return parent[p];
}
};
``````

Above code yield runtime error for following input:

``````[45,30,46,10,36,null,49,8,24,34,42,48,null,4,9,14,25,31,35,41,43,47,null,0,6,null,null,11,20,null,28,null,33,null,null,37,null,null,44,null,null,null,1,5,7,null,12,19,21,26,29,32,null,null,38,null,null,null,3,null,null,null,null,null,13,18,null,null,22,null,27,null,null,null,null,null,39,2,null,null,null,15,null,null,23,null,null,null,40,null,null,null,16,null,null,null,null,null,17], node with value 47, node with value 15
``````

But when I printed `parent[p]` and `parent[p]->val` just before returning, it showed valid output: `37`

Why runtime error? Thanks in advance.

• ``````// I recorded the parents of both p and q.
// Then I compare their parents.
/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> v1, v2;
dfs(root,p,v1);
dfs(root,q,v2);
for(int i=0;i<v1.size();i++){
for(int j=0;j<v2.size();j++){
if(v1[i]==v2[j]){
return v1[i];
}
}
}
return root;
}
bool dfs(TreeNode* root, TreeNode* p, vector<TreeNode*> &v){
if(root==p){
v.push_back(root);
return true;
}
if(root==NULL)return false;
bool s1=dfs(root->left,p,v);
bool s2=dfs(root->right,p,v);
if(s1||s2)v.push_back(root);
return s1||s2;
}
};``````

• I didn't ask for source code. Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.