Select Page

# Find LCA for K queries in Complete Binary Tree

Team 1 - Programming
Published: January 19, 2023

Given an integer n. There is a complete binary tree with 2n – 1 nodes. The root of that tree is the node with the value 1, and every node with a value x has two children where the left node has the value
2*x and the right node has the value 2*x + 1, you are given K queries of type (ai, bi), and the task is to return the LCA for the node pair ai and bi for all K queries.

Examples:

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

Complete binary tree for given input n=5

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

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

Complete binary tree for given input n=3

Output: [2, 3, 1, 3]

Approach: The problem can be solved based on the following idea:

As all values on a level are smaller than values on the next level. Check which node is having greater value in a query, and divide it by 2 to reach its parent node. Repeat this step until we get common element.

Follow the steps to solve the problem:

• In a query, we are having 2 nodes a and b, whose lowest common ancestor we have to find.
• By dividing the value of the node by 2, we will always get the parent node value.
• From a and b whichever node is having greater value divide by 2. So, as to move towards the root of the root.
• When a and b becomes equal, the common ancestor between them is got and returned.

Below is the implementation for the approach discussed:

## C++

 `#include ``using` `namespace` `std;`` ` `int` `helper(``int` `a, ``int` `b)``{`` ` `    ``while` `(a != b) {`` ` `        ``if` `(a > b)``            ``a = a / 2;`` ` `        ``else``            ``b = b / 2;``    ``}`` ` `    ``return` `a;``}`` ` `int` `main()``{`` ` `    ``    ``    ``int` `n = 5;`` ` `    ``    ``vector > queries``        ``= { { 17, 21 }, { 23, 5 }, { 15, 7 }, { 3, 21 }, { 31, 9 }, { 5, 15 }, { 11, 2 }, { 19, 7 } };`` ` `    ``    ``    ``for` `(``auto` `e : queries) {`` ` `        ``        ``int` `lca = helper(e[0], e[1]);`` ` `        ``cout << lca << ``' '``;``    ``}`` ` `    ``return` `0;``}`

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

Related Articles:

Source: www.geeksforgeeks.org