fork(2) download
copy 
  1. /**
  2.  * Lowest Common Ancestor (BST)
  3.  * 
  4.  * http://e...content-available-to-author-only...x.com/2013/11/03/lowest-common-ancestor-bst/
  5.  * 
  6.  */
  7.  
  8. #include <memory>
  9. #include <string>
  10. #include <iostream>
  11.  
  12. namespace evilrix {
  13.    namespace mostlycoding {
  14.  
  15.       /**
  16.        * @brief A node object for our tree, below.
  17.        *
  18.        * @tparam T Generic type parameter representing our data.
  19.        */
  20.  
  21.       template <typename T>
  22.       struct Node
  23.       {
  24.          using Data = T;    ///< The data
  25.          using PNode = std::shared_ptr<Node<Data>>;    ///< The node
  26.  
  27.          /**
  28.           * @brief Initializes a new instance of the main class.
  29.           *
  30.           * @param data (Optional) the data.
  31.           */
  32.  
  33.          Node(Data const & data = 0) : data(data) {}
  34.  
  35.          PNode plhs; ///< The plhs
  36.          PNode prhs; ///< The prhs
  37.          Data data;  ///< The data
  38.       };
  39.  
  40.       /**
  41.        * @brief A tree, implemented as a BST.
  42.        *
  43.        * @tparam T T Generic type parameter representing our data.
  44.        */
  45.  
  46.       template <typename T>
  47.       class Tree
  48.       {
  49.       public:
  50.          using Data = T;    ///< The data
  51.          using PNode = std::shared_ptr<Node<Data>>;    ///< The node
  52.  
  53.          /**
  54.           * @brief Initializes a new instance of the main class.
  55.           */
  56.  
  57.          Tree() {}
  58.  
  59.          /**
  60.           * @brief Inserts the given data.
  61.           *
  62.           * @param data The data.
  63.           */
  64.  
  65.          void insert(Data const & data)
  66.          {
  67.             PNode * pproot = &proot_;
  68.  
  69.             // see my note in the "find_lca" function as to why I am using an
  70.             // iterative rather than recursive traversal approach.
  71.             while (*pproot)
  72.             {
  73.                pproot = data < (*pproot)->data ?
  74.                   &(*pproot)->plhs : &(*pproot)->prhs;
  75.             }
  76.  
  77.             (*pproot) = PNode(new Node<Data>(data));
  78.          }
  79.  
  80.          /**
  81.           * @brief Searches for the first lca.
  82.           *
  83.           * @param x The first data item.
  84.           * @param y The second data item.
  85.           *
  86.           * @return The found lca data item.
  87.           */
  88.  
  89.          PNode find_lca(Data const & x, Data const & y) const
  90.          {
  91.             PNode const * pproot = &proot_;
  92.  
  93.             // Whilst tree traversal is normally done using recursion I've
  94.             // opted for iterative just because it's easier to visualise what's
  95.             // happening. Also, unless your compiler supports "tail recursion"
  96.             // there is always a danger that the recursive approach could blow
  97.             // up. Even if it doesn't, recursion is has a O(n) space complexity
  98.             // whereas iteration has a O(1) space complexity. Both have a time
  99.             // complexity of O(n), assuming no branching is required.
  100.             while (*pproot)
  101.             {
  102.                // traverse down the left hand side?
  103.                if (x < (*pproot)->data && y < (*pproot)->data)
  104.                {
  105.                   pproot = &(*pproot)->plhs;
  106.                }
  107.                else
  108.                // traverse down the right hand side?
  109.                if (x >(*pproot)->data && y >(*pproot)->data)
  110.                {
  111.                   pproot = &(*pproot)->prhs;
  112.                }
  113.                else
  114.                {
  115.                   // we've reached the divisor so this node is the LCA
  116.                   break;
  117.                }
  118.             }
  119.  
  120.             return (*pproot);
  121.          }
  122.  
  123.          PNode proot_;
  124.       };
  125.    }
  126. }
  127.  
  128. using namespace evilrix::mostlycoding;
  129.  
  130. /**
  131.  * @brief Main entry-point for this application.
  132.  *
  133.  * @return Exit-code for the process - 0 for success, else an error code.
  134.  */
  135.  
  136. int main(/* int argc, char * argv[] */)
  137. {
  138.    /*
  139.     *         8
  140.     *        / \
  141.     *      (3)   9
  142.     *      / \
  143.     *   [1]   6
  144.     *        / \
  145.     *       4   [7]
  146.     */
  147.  
  148.    Tree<int> tree;
  149.    tree.insert(8);
  150.    tree.insert(3);
  151.    tree.insert(1);
  152.    tree.insert(6);
  153.    tree.insert(4);
  154.    tree.insert(7);
  155.    tree.insert(9);
  156.  
  157.    Tree<int>::PNode pnode = tree.find_lca(1, 7);
  158.  
  159.    std::cout << (pnode ? std::to_string(pnode->data) : "(null)") << std::endl;
  160. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/SoUaI1
Lowest Common Ancestor (BST)
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!