# Lowest Common Ancestor of a Binary Search Tree

(Referring to this leetcode problem)

I opted for a (relatively) inefficient solution for the following reasons:

• We don’t know whether this BST has any duplicate elements.
• The required C++ function signature is `(TreeNode* root, TreeNode* p, TreeNode* q)`. It could’ve been `(TreeNode* root, int p, int q)`, for example. This fact, coupled with the previous point, suggests that object identity matters.

Moreover, consider the following tree:

``````        _______6______
/              \
_6(a)_          ___6__
/      \        /      \
6(p)   _6       6       6
/  \
6   6(q)
``````

All nodes’ values are `6`, yet we are passed `p` and `q` pointing to specific nodes. The answer in this case must be exactly `a` and not any other `6`-valued node.

So, my algorithm consists of:

1. Let `p_path` be the inclusive path from `root` to `p`, and similarly for `q_path`.
2. The solution is the last element of the largest common prefix between `p_path` and `q_path`.

The (unoptimized) code:

``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
auto p_path = findPath(root, p);
auto q_path = findPath(root, q);

assert(p_path.size() > 0);
assert(q_path.size() > 0);
assert(p_path == root);
assert(q_path == root);
assert(p_path.back() == p);
assert(q_path.back() == q);

int i = 1;
for (; i < min(p_path.size(), q_path.size()); ++i) {
if (p_path[i] != q_path[i]) {
break;
}
}

assert(p_path[i - 1] == q_path[i - 1]);

return p_path[i - 1];
}

vector<TreeNode*> findPath(TreeNode* haystack, TreeNode* needle, vector<TreeNode*> path = {}) {
path.push_back(haystack);
if (needle->val < haystack->val)
return findPath(haystack->left, needle, path);
if (needle->val > haystack->val)
return findPath(haystack->right, needle, path);
// so, values are equal. we must explore all equal-value nodes
path.pop_back(); // so we don't get dupes
return findEq(haystack, needle, path);
}

vector<TreeNode*> findEq(TreeNode* haystack, TreeNode* needle, vector<TreeNode*> path = {}) {
path.push_back(haystack);
if (haystack == needle) {
return path;
}
if (haystack->left && haystack->left->val == needle->val) {
auto maybe = findEq(haystack->left, needle, path);
if (!maybe.empty())
return maybe;
}
if (haystack->right && haystack->right->val == needle->val) {
auto maybe = findEq(haystack->right, needle, path);
if (!maybe.empty())
return maybe;
}
return {};
}
};
``````