Discover LCA for Ok queries in Full Binary Tree

by


Given an integer n. There’s a full binary tree with 2n – 1 nodes. The basis of that tree is the node with the worth 1, and each node with a worth x has two youngsters the place the left node has the worth 
2*x and the proper node has the worth 2*x + 1, you might be given Ok queries of kind (ai, bi), and the duty is to return the LCA for the node pair ai and bi for all Ok queries.

Examples:

Enter:  n = 5, queries = [ { 17, 21 }, { 23, 5 }, { 15, 7 }, { 3, 21 }, { 31, 9 }, { 5, 15 }, { 11, 2 }, { 19, 7 } ]

Full binary tree for given enter n=5

Output:  [ 2, 5, 7, 1, 1, 1, 2, 1 ]

Enter:  n = 3, queries = [ {2, 5}, {3, 6}, {4, 1}, {7, 3} ]

Full binary tree for given enter n=3

Output: [2, 3, 1, 3]

Strategy: The issue will be solved based mostly on the next thought:

As all values on a degree are smaller than values on the following degree. Examine which node is having larger worth in a question, and divide it by 2 to succeed in its mother or father node. Repeat this step till we get widespread factor. 

Observe the steps to unravel the issue:

  • In a question, we’re having 2 nodes a and b, whose lowest widespread ancestor now we have to search out.
  • By dividing the worth of the node by 2, we are going to all the time get the mother or father node worth.
  • From a and b whichever node is having larger worth divide by 2. So, as to maneuver in the direction of the foundation of the foundation.
  • When a and b turns into equal, the widespread ancestor between them is acquired and returned.  

Under is the implementation for the strategy mentioned:

C++

// C++ code for the above strategy
#embrace <bits/stdc++.h>
utilizing namespace std;

// Operate to search out lca for
// given two nodes in tree
int helper(int a, int b)
{

    whereas (a != b) {

        if (a > b)
            a = a / 2;

        else
            b = b / 2;
    }

    return a;
}

// Driver code
int principal()
{

    // 2^n - 1 nodes in full
    // binary tree
    int n = 5;

    // Queries enter vector
    vector<vector<int> > queries
        = { { 17, 21 }, { 23, 5 }, { 15, 7 }, { 3, 21 }, { 31, 9 }, { 5, 15 }, { 11, 2 }, { 19, 7 } };

    // Processing every question in
    // queries vector
    for (auto e : queries) {

        // Operate name
        int lca = helper(e[0], e[1]);

        cout << lca << ' ';
    }

    return 0;
}

Time Complexity: O(n)
Auxiliary Area: O(1)

Associated Articles:

Leave a Comment