fork download
copy 
  1. /**
  2. * Lowest Common Ancestor (non-BST)
  3. * 
  4. * http://e...content-available-to-author-only...x.com/2013/11/12/lowest-common-ancestor-non-bst/
  5. * 
  6. */
  7.  
  8. #include <memory>
  9. #include <string>
  10. #include <iostream>
  11. #include <vector>
  12. #include <algorithm>
  13.  
  14. namespace evilrix {
  15.    namespace mostlycoding {
  16.       /**
  17.       * @brief A node object for our tree, below.
  18.       *
  19.       * @tparam T Generic type parameter representing our data.
  20.       */
  21.  
  22.       template <typename T>
  23.       struct Node
  24.       {
  25.          using Data = T;    ///< The data
  26.          using PNode = std::shared_ptr<Node<Data>>;    ///< The node
  27.  
  28.          /**
  29.          * @brief Initializes a new instance of the main class.
  30.          *
  31.          * @param data (Optional) the data.
  32.          */
  33.  
  34.          Node(Data const & data = 0) : data(data) {}
  35.  
  36.          PNode plhs; ///< The plhs
  37.          PNode prhs; ///< The prhs
  38.          Data data;  ///< The data
  39.       };
  40.  
  41.       /**
  42.       * @brief A tree, implemented as a BST.
  43.       *
  44.       * @tparam T T Generic type parameter representing our data.
  45.       */
  46.  
  47.       template <typename T>
  48.       class Tree
  49.       {
  50.       public:
  51.          using Data = T;    ///< The data
  52.          using PNode = std::shared_ptr<Node<Data>>;    ///< The node
  53.  
  54.          /**
  55.          * @brief Initializes a new instance of the main class.
  56.          */
  57.  
  58.          Tree() {}
  59.  
  60.          /**
  61.          * @brief Inserts the given data.
  62.          *
  63.          * @param data The data.
  64.          */
  65.  
  66.          void insert(Data const & data)
  67.          {
  68.             PNode * pproot = &proot_;
  69.  
  70.             // see my note in the "find_lca" function as to why I am using an
  71.             // iterative rather than recursive traversal approach.
  72.             while (*pproot)
  73.             {
  74.                pproot = data < (*pproot)->data ?
  75.                   &(*pproot)->plhs : &(*pproot)->prhs;
  76.             }
  77.  
  78.             (*pproot) = PNode(new Node<Data>(data));
  79.          }
  80.  
  81.          /**
  82.           * @brief Uses a DFS to find a route to the node with data value 'd'
  83.           *
  84.           * @param d              The Data node to file.
  85.           * @param [in,out] route The route.
  86.           * @param ppnode         The start node.
  87.           *
  88.           * @return true if it succeeds, false if it fails.
  89.           */
  90.  
  91.          bool find_route(Data const & d, std::vector<PNode> & route, PNode const * ppnode) const
  92.          {
  93.             if (!ppnode || !(*ppnode))
  94.             {
  95.                return false;
  96.             }
  97.  
  98.             if ((*ppnode)->data == d)
  99.             {
  100.                route.push_back(*ppnode);
  101.                return true;
  102.             }
  103.  
  104.             if (find_route(d, route, &(*ppnode)->plhs))
  105.             {
  106.                route.push_back(*ppnode);
  107.                return true;
  108.             }
  109.  
  110.             if (find_route(d, route, &(*ppnode)->prhs))
  111.             {
  112.                route.push_back(*ppnode);
  113.                return true;
  114.             }
  115.  
  116.             return false;
  117.          }
  118.  
  119.          /**
  120.           * @brief Searches for the first lca.
  121.           *
  122.           * @param x The Data find.
  123.           * @param y The Data find.
  124.           *
  125.           * @return The found lca.
  126.           */
  127.  
  128.          PNode find_lca(Data const & x, Data const & y) const
  129.          {
  130.             std::vector<PNode> routex;
  131.             find_route(x, routex, &proot_);
  132.  
  133.             std::vector<PNode> routey;
  134.             find_route(y, routey, &proot_);
  135.  
  136.             PNode result;
  137.  
  138.             while (
  139.                !routex.empty() &&
  140.                !routey.empty() &&
  141.                routex.back()->data == routey.back()->data
  142.                )
  143.             {
  144.                result = routex.back();
  145.                routex.pop_back();
  146.                routey.pop_back();
  147.             }
  148.  
  149.             return result;
  150.          }
  151.  
  152.          PNode proot_;
  153.       };
  154.    }
  155. }
  156.  
  157. using namespace evilrix::mostlycoding;
  158.  
  159. /**
  160. * @brief Main entry-point for this application.
  161. *
  162. * @return Exit-code for the process - 0 for success, else an error code.
  163. */
  164.  
  165. int main(/* int argc, char * argv[] */)
  166. {
  167.    /*
  168.    *         8
  169.    *        / \
  170.    *      (3)   9
  171.    *      / \
  172.    *   [1]   6
  173.    *        / \
  174.    *       4   [7]
  175.    */
  176.  
  177.    Tree<int> tree;
  178.    tree.insert(8);
  179.    tree.insert(3);
  180.    tree.insert(1);
  181.    tree.insert(6);
  182.    tree.insert(4);
  183.    tree.insert(7);
  184.    tree.insert(9);
  185.  
  186.    Tree<int>::PNode pnode1 = tree.find_lca(1, 7);
  187.    std::cout << (pnode1 ? std::to_string(pnode1->data) : "(null)") << std::endl;
  188. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/xEh0YH
Lowest Common Ancestor (non-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!