## Lowest Common Ancestor Code

Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.

```#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>

using namespace std;

class Node {

public:

Node() {
}

vector<Node *> children;
Node *parent;
};

Node *make_random_tree(size_t size,Node *root=NULL) {

if(root == NULL) {
root = new Node();
}

Node *current = root;

size_t children=rand()%size;
for(size_t i=0;i<children;i++) {
Node *nd = new Node();
nd->parent = current;
current->children.push_back(nd);
}

for(size_t n=0;n<current->children.size();n++) {
make_random_tree(size-children,current->children[n]);
}

return root;
}

Node *get_random(Node *root,size_t avg_size) {

Node *current = root;
for(;rand()%(avg_size*2) != 0;) {
if(current->children.size() == 0) return current;

current = current->children[rand()%current->children.size()];
}

return current;
}

Node * get_next_child(Node *node,Node *child) {

bool next=false;
for(size_t n=0;n<node->children.size();n++) {

if(next==true) {
return node->children[n];
}

if(node->children[n] == child) next=true;
}

return NULL;
}

vector<Node *> get_path(Node *root,Node *n) {

vector<Node *> current_path;
current_path.push_back(root);

if(n==root) return current_path;

Node *current_child = root->children[0];

for(;;) {

current_path.push_back(current_child);
if(current_child == n) return current_path;

if(current_child->children.size() != 0) {
current_path.push_back(current_child->children[0]);
current_child = current_child->children[0];
} else {
current_child = NULL;
for(;current_child == NULL;) {
Node *old_child = current_path[current_path.size()-1];
current_path.erase(current_path.begin()+current_path.size()-1,current_path.end());
current_child = get_next_child(current_path[current_path.size()-1],old_child);

if(old_child==root) { return vector<Node *>(); }
}
}
}

// Should never get here
return vector<Node *>();
}

vector<Node *> get_path_parent(Node *root,Node *n) {

vector<Node *> v;

for(Node *current = n;current != root;current = current->parent) {
v.push_back(current);
}
v.push_back(root);

reverse(v.begin(),v.end());

return v;
}

Node *find_lca_parent(Node *root,Node *n1,Node *n2) {

vector<Node *> path1 = get_path_parent(root,n1);
vector<Node *> path2 = get_path_parent(root,n2);

for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl;
for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl;

size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();

size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);

return path1[n-1];
}

Node *find_lca(Node *root,Node *n1,Node *n2) {

vector<Node *> path1 = get_path(root,n1);
vector<Node *> path2 = get_path(root,n2);

size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();

size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);

return path1[n-1];
}

int main() {

Node *root = make_random_tree(100);

Node *n1 = get_random(root,20);
Node *n2 = get_random(root,20);

Node *lca1a = find_lca_parent(root,n1,n2);
Node *lca1b = find_lca       (root,n1,n2);

cout << "LCA1-a: " << lca1a << endl;
cout << "LCA1-b: " << lca1a << endl;

Node *n3 = root->children[0]->children[0]->children[0];
Node *n4 = root->children[0]->children[0]->children[1];
Node *lca2a = find_lca_parent(root,n3,n4);
Node *lca2b = find_lca       (root,n3,n4);

cout << "LCA2-a: " << lca2a << endl;
cout << "LCA2-b: " << lca2b << endl;
}
```