// Given a binary tree, find the lowest common ancestor(LCA) of two given nodes in the tree.Assume that each node in the tree also has
// a pointer to its parent.
// According to the definition of LCA on Wikipedia : “The lowest common ancestor is defined between two nodes v and w as the lowest node
// in T that has both v and w as descendants(where we allow a node to be a descendant of itself).”
// I assumed that each entry is unique in the tree to make my solution simpler
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <sstream>
#include <thread>
#include <map>
#include <vector>
#include <string>
using namespace std;
class Node
{
public:
int value;
Node* left = nullptr;
Node* right = nullptr;
Node* parent = nullptr;
Node(int newValue, Node* nodeParent = nullptr)
{
value = newValue;
parent = nodeParent;
}
};
void printPath(vector<int> path)
{
for (unsigned i = 0; i < path.size(); ++i)
{
cout << path[i] << ", ";
}
cout << endl << "---------------" << endl;
}
void getLcaRecurs(struct Node* node, int target, bool& success)
{
if (node == nullptr)
return;
// look for the target value until we find it
if (node->value == target)
{
success = true;
return;
}
else
{
// else: try both subtrees
getLcaRecurs(node->left, target, success);
getLcaRecurs(node->right, target, success);
}
}
Node* getLCA(Node* node1, Node* node2)
{
Node* node = nullptr;
Node* LCA = nullptr;
int target;
bool success = false;
if (node1->value < node2->value)
{
node = node1;
target = node2->value;
}
else
{
node = node2;
target = node1->value;
}
while (node)
{
getLcaRecurs(node, target, success);
if (success)
{
return node;
}
// go back up from node1 until we find a node that can encounter node2
node = node->parent;
}
return LCA;
}
// Example tree
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// / \
//8 9
// the LCA of 2 and 5 is: 1
Node* makeTree()
{
Node* head = new Node(1);
head->left = new Node(2, head);
head->right = new Node(3, head);
head->left->left = new Node(4, head->left);
head->left->right = new Node(5, head->left);
head->left->left->left = new Node(8, head->left->left);
head->left->left->right = new Node(9, head->left->left);
head->right->left = new Node(6, head->right);
head->right->right = new Node(7, head->right);
cout << "Tree constructed" << endl;
return head;
}
int main(int argc, char** argv)
{
auto tree = makeTree();
Node* result = getLCA(tree->left->left->left, tree->left->right);
cout << "LCA Value: " << result->value << endl;
return 0;
}
Comments