Finding LCA using upward traversals

Finding the LCA of node ‘A’ and node ‘B’ by traversing up towards the root node

The idea behind this technique is to traverse upward from each node towards the root node while keeping track of the visited node(s). Since upward traversal requires each node to know its parent, we do an initial depth-first search to find the parent of each node.


Algorithm : Finding the lowest common ancestor (LCA) of two nodes using upward traversal

  1. Find the parent of each node by doing a depth-first traversal. This preprocessing is needed only once before finding the lowest common ancestors of multiple pairs of node in the tree.
  2. Traverse upward from the first node ‘A’ towards the root, mark the nodes along the path as visited.
  3. Traverse upward from the second node ‘B’ towards the root. If a visited node is found in the path of upward traversal, it evidently is the lowest common ancestor since this was marked visited during the traversal from node ‘A’.

Example of finding the lowest common ancestor (LCA) of two nodes using upward traversal

Consider finding the lowest common ancestor of nodes 11 and 8 in the below tree.
Upward traversal from node 8 towards the root yields the path [ 11 7 3 ], all the nodes in the path are marked visited.
Upward traversal from node 11 towards the root takes the path [ 8 3 ]. As soon as the upward traveral from node ‘8’ encounters a visited node ‘3’ in the path, the algorithm returns ‘3’ as the lowest common ancestor as it was visited during an earlier traversal and hence must be the lowest common ancestor.

Lowest_Common_Ancestor_Upward_Traversal

Data structure for storing tree: Adjacency List
Data structure for storing parent nodes: list / vector
Time complexity of finding the LCA using upward traversals : O(N), where N is the number of nodes in the tree. If the tree is unbalanced i.e in the worst case if every node of the tree has only one node, the tree becomes linear with height = N. If we have to find the lowest common ancestor “M” times, the time complexity becomes N*M, as for every query (M) we have to traverse the height of the tree.


C++14 Finding the Lowest Common Ancestor (LCA) using upward traversal

#include<iostream>
#include<list>
#include<vector>

using namespace std;

class Tree{

    private:
        list<int> *adjlist;
        vector<int> parentlist;
        vector<bool> visited;
    
    public:
        Tree() {
        }

        Tree (int nodes) { 
            adjlist = new list<int> [nodes];
            parentlist.resize(nodes);
            visited.resize(nodes);
        }

        ~Tree() { 
            delete [] adjlist;
        }

        void AddEdge(int src, int dst) {
            adjlist[src].push_back(dst);
            adjlist[dst].push_back(src);
        }

        // Get parent of every node 
        void GetParent(int node, int parent){
    
             for(auto& v : adjlist[node]) {
                 if (v != parent) {
                    parentlist[v] = node;
                    GetParent(v, node);
                 }
             }
        }

        int GetLCA(int root_node, int node_a, int node_b){
    
            int lca = root_node;

            // Traverse from node_a upto the root node;
            while (true) {
                visited[node_a] = true;
                if (node_a == root_node) {
                    break;
                }
                node_a = parentlist[node_a];
            }

            /* Travese from node_b up to the root node. If along the path a visited parent is found,
               it is the LCA of (node_a, node_b) */
            while (true){
                if (visited[node_b]) {
                    lca = node_b;
                    break;
                }
                node_b = parentlist[node_b];
            }
            return lca;
        }
};

int main(){

    Tree t(15);

    t.AddEdge(0,1);
    t.AddEdge(0,2);
    t.AddEdge(0,3);
    t.AddEdge(1,4);
    t.AddEdge(1,5);
    t.AddEdge(1,6);
    t.AddEdge(3,7);
    t.AddEdge(3,8);
    t.AddEdge(4,9);
    t.AddEdge(7,11);
    t.AddEdge(9,10);
    t.AddEdge(11,12);
    t.AddEdge(11,13);
    t.AddEdge(11,14);

    // Root node does not have any parent; so set it to -1
    t.GetParent(0, -1);
    int root_node = 0;
    cout << "LCA of (10, 13) : " << t.GetLCA(root_node, 10, 13) << endl;
    cout << "LCA of (4, 6)   : " << t.GetLCA(root_node, 4, 6) << endl;
    cout << "LCA of (11, 8)  : " << t.GetLCA(root_node, 11, 8) << endl;
    cout << "LCA of (0, 2)   : " << t.GetLCA(root_node, 0, 2) << endl;
    cout << "LCA of (6, 0)   : " << t.GetLCA(root_node, 6, 0) << endl;
    cout << "LCA of (14, 8)  : " << t.GetLCA(root_node, 14, 8) << endl;

    return 0;
}

Output

LCA of (10, 13) : 0
LCA of (4, 6)   : 1
LCA of (11, 8)  : 3
LCA of (0, 2)   : 0
LCA of (6, 0)   : 0
LCA of (14, 8)  : 3

Copyright (c) 2019-2020, Algotree.org.
All rights reserved.