Finding LCA in a binary tree / multinode tree using upward traversals

The idea 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.

Note : The parent node in a tree can have more than 2 children nodes.

Algorithm

  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 nodes 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’.

Lowest_Common_Ancestor_Upward_Traversal Example

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 [ 8 3 0 ], all the nodes in the path are marked visited.
Upward traversal from node 11 towards the root takes the path [ 11 7 3 0 ].

When the upward traveral from node ‘11’ 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.

Similary consider finding the LCA of node 0 and node 2.
Upward traversal path of node 2 is [ 2 0 ]. Nodes 2, 0 are marked visited.
Upward traversal path of node 0 is [ 0 ].
When a visited node 0 is encountered during upward traversal of node 0, it evidently becomes the lowest common ancestor of node 0 and node 2.





Data structure for storing tree: Adjacency List
Data structure for storing parent nodes: list / vector
Time complexity : 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.

Program for finding the Lowest Common Ancestor (LCA) in a binary / multinode tree 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);
    
    // AddEdge (Parent, Child)
    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

import java.util.ArrayList;
import java.util.List;

class Tree {

    private List<List<Integer>> adjlist;
    private List<Integer> parentlist;
    private List<Boolean> visited;

    Tree (int nodes) {

        adjlist = new ArrayList<>(nodes);
        parentlist = new ArrayList<>(nodes);
        visited = new ArrayList<>(nodes);

        for (int i = 0; i < nodes; i++) {
            adjlist.add(new ArrayList<>());
            parentlist.add(-1); //initialize the parrent array
            visited.add(false); //initialize the visited array
        }
    }

    void AddEdge (int src, int dst) {
        adjlist.get(src).add(dst);
        adjlist.get(dst).add(src);
    }

    //Get Parent of every node
    void GetParent (int node, int parent) {

        for (int v : adjlist.get(node)) {
            if (v != parent) {
                parentlist.set(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.set(node_a, true);
            if (node_a == root_node) {
                break;
            }
            node_a = parentlist.get(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.get(node_b)) {
                lca = node_b;
                break;
            }
            node_b = parentlist.get(node_b);
        }
        return lca;
    }

    public static void main (String args[]) {

        Tree t = new Tree(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;

        System.out.println("LCA of (10, 13) : " + t.GetLCA(root_node, 10, 13));
        System.out.println("LCA of (4, 6)   : " + t.GetLCA(root_node, 4, 6));
        System.out.println("LCA of (11, 8)  : " + t.GetLCA(root_node, 11, 8));
        System.out.println("LCA of (0, 2)   : " + t.GetLCA(root_node, 0, 2));
        System.out.println("LCA of (6, 0)   : " + t.GetLCA(root_node, 6, 0));
        System.out.println("LCA of (14, 8)  : " + t.GetLCA(root_node, 14, 8));
    }
}

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-2024, Algotree.org.
All rights reserved.