/**
* Lowest Common Ancestor (non-BST)
*
* http://e...content-available-to-author-only...x.com/2013/11/12/lowest-common-ancestor-non-bst/
*
*/
#include <memory>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
namespace evilrix {
namespace mostlycoding {
/**
* @brief A node object for our tree, below.
*
* @tparam T Generic type parameter representing our data.
*/
template <typename T>
struct Node
{
using Data = T; ///< The data
using PNode = std::shared_ptr<Node<Data>>; ///< The node
/**
* @brief Initializes a new instance of the main class.
*
* @param data (Optional) the data.
*/
Node(Data const & data = 0) : data(data) {}
PNode plhs; ///< The plhs
PNode prhs; ///< The prhs
Data data; ///< The data
};
/**
* @brief A tree, implemented as a BST.
*
* @tparam T T Generic type parameter representing our data.
*/
template <typename T>
class Tree
{
public:
using Data = T; ///< The data
using PNode = std::shared_ptr<Node<Data>>; ///< The node
/**
* @brief Initializes a new instance of the main class.
*/
Tree() {}
/**
* @brief Inserts the given data.
*
* @param data The data.
*/
void insert(Data const & data)
{
PNode * pproot = &proot_;
// see my note in the "find_lca" function as to why I am using an
// iterative rather than recursive traversal approach.
while (*pproot)
{
pproot = data < (*pproot)->data ?
&(*pproot)->plhs : &(*pproot)->prhs;
}
(*pproot) = PNode(new Node<Data>(data));
}
/**
* @brief Uses a DFS to find a route to the node with data value 'd'
*
* @param d The Data node to file.
* @param [in,out] route The route.
* @param ppnode The start node.
*
* @return true if it succeeds, false if it fails.
*/
bool find_route(Data const & d, std::vector<PNode> & route, PNode const * ppnode) const
{
if (!ppnode || !(*ppnode))
{
return false;
}
if ((*ppnode)->data == d)
{
route.push_back(*ppnode);
return true;
}
if (find_route(d, route, &(*ppnode)->plhs))
{
route.push_back(*ppnode);
return true;
}
if (find_route(d, route, &(*ppnode)->prhs))
{
route.push_back(*ppnode);
return true;
}
return false;
}
/**
* @brief Searches for the first lca.
*
* @param x The Data find.
* @param y The Data find.
*
* @return The found lca.
*/
PNode find_lca(Data const & x, Data const & y) const
{
std::vector<PNode> routex;
find_route(x, routex, &proot_);
std::vector<PNode> routey;
find_route(y, routey, &proot_);
PNode result;
while (
!routex.empty() &&
!routey.empty() &&
routex.back()->data == routey.back()->data
)
{
result = routex.back();
routex.pop_back();
routey.pop_back();
}
return result;
}
PNode proot_;
};
}
}
using namespace evilrix::mostlycoding;
/**
* @brief Main entry-point for this application.
*
* @return Exit-code for the process - 0 for success, else an error code.
*/
int main(/* int argc, char * argv[] */)
{
/*
* 8
* / \
* (3) 9
* / \
* [1] 6
* / \
* 4 [7]
*/
Tree<int> tree;
tree.insert(8);
tree.insert(3);
tree.insert(1);
tree.insert(6);
tree.insert(4);
tree.insert(7);
tree.insert(9);
Tree<int>::PNode pnode1 = tree.find_lca(1, 7);
std::cout << (pnode1 ? std::to_string(pnode1->data) : "(null)") << std::endl;
}