LCA in a tree

Lowest Common Ancestor of List of Values

/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
Tree* helper(Tree* node, unordered_set<int>& s, int &cnt, int target){
if (node == nullptr) {
cnt = 0;
return nullptr;
}
int l = 0, r =0;
auto le = helper(node -> left, s, l, target);
auto ri = helper(node -> right, s, r, target);
int thiscnt = 0;
if (s.find(node -> val) != s.end()) thiscnt = 1;
cnt = l + r + thiscnt;
if (thiscnt && thiscnt + l + r == target) return node;
if (!thiscnt && l + r == target && l && r) return node;
//if (l + r == target) return node;
if (l == target) return le;
if (r == target) return ri;
if (l + r + thiscnt < target) return nullptr;

return nullptr;
}
Tree* solve(Tree* root, vector<int>& values) {
unordered_set<int> s(values.begin(), values.end());
int n = values.size();
int cnt = 0;
return helper(root, s, cnt, n);

}
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
Tree* helper(Tree* root, unordered_set<int>&s){
if (root == nullptr) return root;
auto l = helper(root->left, s);
auto r = helper(root->right, s);
if (s.find(root->val) != s.end()) {
return root;
}
if (l && r) return root;
return l? l: r;
}
Tree* solve(Tree* root, vector<int>& values) {
unordered_set<int> s(values.begin(), values.end());
return helper(root, s);
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi