/**
* Lowest Common Ancestor (BST)
*
* http://e...content-available-to-author-only...x.com/2013/11/03/lowest-common-ancestor-bst/
*
*/
#include <memory>
#include <string>
#include <iostream>
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 Searches for the first lca.
*
* @param x The first data item.
* @param y The second data item.
*
* @return The found lca data item.
*/
PNode find_lca(Data const & x, Data const & y) const
{
PNode const * pproot = &proot_;
// Whilst tree traversal is normally done using recursion I've
// opted for iterative just because it's easier to visualise what's
// happening. Also, unless your compiler supports "tail recursion"
// there is always a danger that the recursive approach could blow
// up. Even if it doesn't, recursion is has a O(n) space complexity
// whereas iteration has a O(1) space complexity. Both have a time
// complexity of O(n), assuming no branching is required.
while (*pproot)
{
// traverse down the left hand side?
if (x < (*pproot)->data && y < (*pproot)->data)
{
pproot = &(*pproot)->plhs;
}
else
// traverse down the right hand side?
if (x >(*pproot)->data && y >(*pproot)->data)
{
pproot = &(*pproot)->prhs;
}
else
{
// we've reached the divisor so this node is the LCA
break;
}
}
return (*pproot);
}
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 pnode = tree.find_lca(1, 7);
std::cout << (pnode ? std::to_string(pnode->data) : "(null)") << std::endl;
}