Lowest Common Ancestor
========================================

- With Parent Link

    .. code-block:: cpp

        Node *LCA(Node *n1, Node *n2) {
            set <Node*> ancestors;
            while (n1 != NULL) {
                ancestors.insert(n1);
                n1 = n1->parent;
            }
            while (n2 != NULL) {
                if (ancestors.count(n2))
                    return n2;
                n2 = n2->parent;
            }
            return NULL;
        }

- Without Parent Link

    .. code-block:: cpp

        int depth(Node *node) {
            int d = -1;
            while (node) {
                ++d, node = node->parent;
            }
            return d;
        }

        Node *LCA(Node *n1, Node *n2) {
            int d1 = depth(n1), d2 = depth(n2);
            if (d1 < d2) {
                swap(n1, n2), swap(d1, d2);
            }
            while (d1 != d2) {
                d2++; 
                n1 = n1->parent;
            }

            while (1) {
                if (n1 == n2) return n1;
                n1 = n1->parent, n2 = n2->parent;
            }
            return NULL;
        }

.. only:: html

    - `Lowest Common Ancestor of a Binary Tree on LeetCode <https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/>`_
    - `Lowest Common Ancestor of a Binary Search Tree on LeetCode <https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/>`_