1650. Lowest Common Ancestor of a Binary Tree III

 Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q exist in the tree.

/*

// Definition for a Node.

class Node {

public:

    int val;

    Node* left;

    Node* right;

    Node* parent;

};

*/

class Solution {

public:

    Node* lowestCommonAncestor(Node* p, Node * q) {

        unordered_set<Node*> st;

        while (st.count(p) == 0) {

            if (p == NULL) {

                break;

            }

            st.insert(p);

            p = p -> parent;

        }

        

        Node *ans = NULL;

        while (1) {

            if (q == NULL) {

                break;

            }

            if (st.count(q) != 0) {

                return q;

            } else {

                q = q -> parent;

                if (q == q -> parent) {

                    return NULL;

                }

            }

        }

        return NULL;

    }

};

/*

// Another approach ....

 Node* lowestCommonAncestor(Node* p, Node * q) {

        // search upwards from p and q, adding each found node to a set

        // if the node being added that is reachable from either p or q already exists in the set

        // then we have found the lowest common ancestor

        

        std::unordered_set<Node*> parents = {};

        

        Node* s = p;

        Node* t = q;

        while (s != nullptr || t != nullptr) {

            if (s != nullptr) {

                if (parents.find(s) != parents.end())

                    return s;

                parents.insert(s);

                s = s->parent;

            }

            if (t != nullptr) {

                if (parents.find(t) != parents.end())

                    return t;

                parents.insert(t);

                t = t->parent;

            }

        }

        return nullptr;

    }

*/