You are viewing a single comment's thread. Return to all comments →
My solution was so convoluted.
vector pathTo(node* root,int key){ vector path; node* current = root; while (current != NULL && current->data != key) { path.push_back(current); if (key data) current = current->left; else if (key > current->data) current = current->right; } if (current) path.push_back(current); return path; } node*lca(node*root,int x,int y){ vector pathX = pathTo(root, x), pathY = pathTo(root, y); unordered_set s; int i; for (i = pathX.size()-1; i >= 0; --i) s.insert(pathX[i]); for (i = pathY.size()-1; i >= 0; --i) { if (!s.insert(pathY[i]).second) break; } return pathY[i]; }
Binary Search Tree : Lowest Common Ancestor
You are viewing a single comment's thread. Return to all comments →
My solution was so convoluted.