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

Idea: 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 store the parent of each node.

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

Algorithm

  1. Store the parent of each node by doing a depth-first traversal. This preprocessing is needed only once before finding the LCAs 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

To find the LCA of nodes 11 and 8 in the below tree.

  • Traverse upwards from node 8 towards the root. This yields the path [ 8 3 0 ].
  • Nodes [ 8 3 0 ] are marked visited.
  • Traverse upwards from node 11 towards the root. This yields 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 LCA as it was marked visited during the earlier traversal and hence must be the LCA.

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 LCA 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.