Lowest Common Ancestor of a Binary Tree III

Leetcode 1650. Lowest Common Ancestor of a Binary Tree III

Problem

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.

Source: Leetcode-1650. Lowest Common Ancestor of a Binary Tree III

Solution

In this problem, each node’s parent pointer is given. So, we can climb up the two nodes and when they meet in a single node, that is the lowest common ancestor. But, the problem is, when the two nodes are in different distance from root node, this approach will not work.

To make it work, we need to find the distance of two nodes from root node. If the distance is not equal, we need to reduce the distance of lower node by climbing up towards root until both the nodes distance are equal (from root).

Once, the distance is equal, we can simply climb up both nodes simultaneously until we reach to a common node which is essentially the lowest common ancestor.

Complexity

Since we are climbing up the tree until root is reached, in worst case, the time complexity will be proportionate to the height of the tree, that is O(N) where N = height of the tree.

We are not using any extra space which can grow proportionate to the input size. So, the space complexity is O(1).

C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    
    int get_distance_from_parent(Node* p){
        if(p == NULL)
            return 0;
        return 1 + get_distance_from_parent(p->parent);
    }
    
    Node* lowestCommonAncestor(Node* p, Node * q) {
        
        int p_dist_parent = 0;
        int q_dist_parent = 0;
        p_dist_parent = get_distance_from_parent(p);
        q_dist_parent = get_distance_from_parent(q);
        /*
           If the two distances are not equal, we will climb up the node
           which is more far away from root than the other node.
        */
        while(p_dist_parent != q_dist_parent){
            if(p_dist_parent < q_dist_parent){
                q = q->parent;
                q_dist_parent--;
            }
            else if(p_dist_parent > q_dist_parent){
                p = p->parent;
                p_dist_parent--;
            }
        }
        /*
        Two nodes are now equal distance from root node. So, we will make both nodes
        climb up at the same time until they both are equal.
       */
        while(p != q){
            p = p->parent;
            q = q->parent;
        }
        return p;
    }
};