Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
What is the Binary Lifting Technique?
2.
The Lowest Common Ancestor Problem
3.
Brute-Force Approach
4.
Binary Lifting Approach
5.
Code
5.1.
C++
5.1.1.
Time Complexity
5.1.2.
Space Complexity
6.
Why to use Binary Lifting?
7.
Use Cases of Binary Lifting
8.
Frequently Asked Questions
8.1.
What is the Lowest Common Ancestor in a Binary Tree?
8.2.
What are the applications of finding LCA in a Binary Tree?
8.3.
What is the time complexity of binary lifting?
9.
Conclusion
Last Updated: Mar 28, 2024
Easy

The Binary Lifting Technique

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

What is the Binary Lifting Technique?

The Binary Lifting Technique is widely used to increase efficiency and subsequently reduce an algorithm’s time complexity. It is a faster algorithm and saves the computational power of the system.

Lowest Common Ancestor - Binary Lifting

There are many problems that we can solve with the Binary Lifting technique. Just to name a few:

  • Finding the Lowest Common Ancestor in a Binary Tree in a logarithmic time.
  • Finding minimum and maximum in a logarithmic time.
  • Finding the sum of two nodes in a logarithmic time.
  • Finding the Kth ancestor of a node in a logarithmic time.

Also see, Data Structures

The Lowest Common Ancestor Problem

The Lowest Common Ancestor of two nodes in a given binary tree is the lowest node that has both the given nodes as its descendants. Also, if one node is the descendant of the other node from the two nodes, then the parent node will be the Lowest Common Ancestor.

 

 

Tree

 

For instance, in this given tree, the Lowest Common Ancestor of nodes 9 and 0 is 6 because 6 is the lowest ascendant of both 9 and 0.

 

The LCA of nodes 9 and 6 is 6 because 9 is the descendant of 6.

 

So, now that the problem is apparent, we’ll see the naive-brute force approach to solve this problem.

Recommended: Do try the Problem yourself first before moving on to the solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Brute-Force Approach

The algorithm for a simple solution to this problem is:

 

  • First, we’ll find the depth (distance from the root node) of both nodes.

 

  • Then we’ll bring the deeper node in the tree to the level of the other node. We’ll do this by making jumps of one (i.e., changing the node value to its parent value).

 

  • When the two nodes are at the same level, if the values of both nodes are the same, we’ll return the value (this is the case when the other node itself is the LCA of both nodes).

 

  • We’ll keep jumping up both nodes one by one till the value of both nodes is not equal. (We can also compare the parent values of both nodes instead of their values)

 

  • Finally, if the values of both nodes are the same, we’ll return the result.

 

This algorithm’s time complexity is O(n), and the space complexity of this brute-force approach is also O(n), where n is the number of nodes in the binary tree.

 

Binary Lifting Approach

The problem with the above approach was that the time complexity was high O(n), So, let’s try to reduce the time complexity by using the Binary Lifting approach.

The idea of the Binary Lifting algorithm is that we reduce the number of upward jumps and hence reduce the number of comparisons.

 

In the brute force approach, we were making the jumps of one unit upwards and then comparing the values of both nodes, but now we’ll lift the nodes in the power of twos.

 

Here, Instead of making an upward jump of one, we’ll make a jump of the highest length j such that:

  • j is a power of 2, and
  • j is less than or equal to the difference between the depths of two nodes.

 

For instance, suppose the difference between the depths of two nodes is 14; according to the brute force solution, we’ll have to do a minimum of 13 comparisons.

But using Binary Lifting, we’ll bring down the number of comparisons down to 3.

 

When, d = 13 j = 8 (because 8 is the highest power of 2 less than d)

d = 5 j = 4

d = 1 j = 1

 

Hence, we can see that the time complexity is significantly reduced to O(logn) because we have reduced the number of comparisons from 13 to 3.

 

Code

  • C++

C++

#include<bits/stdc++.h>
using namespace std;

struct TreeNode{
TreeNode *left;
TreeNode *right;
int val;
TreeNode(int x): left(NULL), right(NULL), val(x){}
};

struct info{
info* pr[30]; int h;
TreeNode* root;
info(){
for(int i=0;i<30;i++)pr[i]=nullptr;
}
};

unordered_map<int,info*>da;
int lgn = 20;
void dfs(TreeNode* root, info* pt, int h){
if(root==nullptr)return;
auto y = da[root->val] = new info;
y->h = h;
y->pr[0] = pt;
y->root = root;
dfs(root->left,y,h+1);
dfs(root->right,y,h+1);
}

void precompute(){
for(int i=1;i<=lgn;i++){
for(auto h=da.begin();h!=da.end();h++){
if(h->second->pr[i-1]!=nullptr)
h->second->pr[i] = h->second->pr[i-1]->pr[i-1];
}
}
}

TreeNode* lca(TreeNode* u, TreeNode* v){
auto p = da[u->val],q = da[v->val];
int diff = p->h - q->h;
if(diff<0)
swap(p,q);
for(int i=lgn;i>=0;i--)
if(p->pr[i]!=nullptr&&p->pr[i]->h>=q->h)
p = p->pr[i];
if(p==q)return p->root; 
for(int i=lgn;i>=0;i--){
if(p->pr[i]!=q->pr[i]){
p = p->pr[i];
q = q->pr[i];
}
}
return p->pr[0]->root;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root,nullptr,0); // compute depth, parent etc
precompute(); // sparse matrix
return lca(p,q); // lca
}

TreeNode *build_tree(int n,char nodes[]){
TreeNode *root = new TreeNode(nodes[0] - '0');
queue<TreeNode*> q;
bool is_left = true;
TreeNode *cur = NULL;
q.push(root);
for(int i = 1; i < n; i++){
TreeNode *node = NULL;
if(nodes[i] != '#'){
node = new TreeNode(nodes[i] - '0');
q.push(node);
}
if(is_left){
cur = q.front();
q.pop();
cur->left = node;
is_left = false;
}else{
cur->right = node;
is_left = true;
}
}
return root;
}

int main(){
int arr_len = 17;
char arr[arr_len] = {'4','1','5','2','6','3','8','#','#','7','0','2','#','#','#','#','9'};
struct TreeNode* root = build_tree(arr_len,arr);

// LCA of nodes 9 and 0
TreeNode* ans1 = lowestCommonAncestor(root, root->left->right->left->right, root->left->right->right);
cout<<"The LCA of nodes 9 and 0 is: "<<ans1->val<<endl;

// LCA of nodes 9 and 6
TreeNode* ans2 = lowestCommonAncestor(root, root->left->right, root->left->right->left->right);
cout<<"The LCA of nodes 9 and 6 is: "<<ans2->val<<endl;

// LCA of nodes 1 and 3
TreeNode* ans3 = lowestCommonAncestor(root, root->left, root->right->left);
cout<<"The LCA of nodes 1 and 3 is: "<<ans3->val<<endl;

// LCA of nodes 8 and 3
TreeNode* ans4 = lowestCommonAncestor(root, root->right->left, root->right->right);
cout<<"The LCA of nodes 8 and 3 is: "<<ans4->val<<endl;

return 0;
}

Input

9 0
9 6
1 3
8 3

 

Output

The LCA of nodes 9 and 0 is: 6
The LCA of nodes 9 and 6 is: 6
The LCA of nodes 1 and 3 is: 4
The LCA of nodes 8 and 3 is: 5

 

Time Complexity

The time complexity of this code is O(logn), where n is the number of nodes in the Binary Tree.

 

Space Complexity

The auxiliary space required by the algorithm is O(n), where n is the number of nodes in the Binary Tree or the size of the Binary Tree.

Read More - Time Complexity of Sorting Algorithms

Why to use Binary Lifting?

Binary lifting is a technique primarily used in the context of trees, particularly for solving problems related to finding the lowest common ancestor (LCA) of two nodes efficiently. It offers several advantages:

  • Efficient LCA Queries: Binary lifting allows for fast computation of the LCA of two nodes in a tree. This is especially valuable in scenarios where multiple LCA queries need to be performed quickly, such as in graph algorithms and tree-based data structures.
  • Optimal Time Complexity: Compared to naive approaches for LCA computation, such as depth-first search (DFS) or breadth-first search (BFS), binary lifting achieves better time complexity, typically O(log N), where N is the number of nodes in the tree. This makes it suitable for large trees or graphs.
  • Simplicity of Implementation: Despite its efficiency, binary lifting is relatively straightforward to implement once understood. It involves pre-processing the tree to compute ancestor relationships efficiently, and then performing queries using bitwise operations.
  • Versatility: While binary lifting is commonly used for LCA computation, it can also be adapted for other tree-related problems, such as finding the kth ancestor of a node, determining the distance between two nodes, or solving dynamic programming tasks on trees.

Use Cases of Binary Lifting

  • Lowest Common Ancestor (LCA) Queries: The primary use case of binary lifting is to efficiently compute the lowest common ancestor of two nodes in a tree. This is crucial in various applications, including genealogy, network routing, and hierarchical data structures.
  • Distance Queries: Binary lifting can be employed to determine the distance between two nodes in a tree efficiently. By first computing the LCA of the nodes and then calculating the distances from each node to the LCA, the total distance between the nodes can be obtained.
  • Kth Ancestor Queries: Another use case of binary lifting is to find the kth ancestor of a given node in a tree. This is useful in scenarios such as finding the parent, grandparent, or nth-level ancestor of a node without traversing the tree repeatedly.
  • Dynamic Programming on Trees: Binary lifting can also be utilized in dynamic programming tasks on trees, where efficient traversal and computation of values based on ancestor relationships are required. This includes problems such as subtree queries, tree path queries, and subtree manipulation tasks.

Frequently Asked Questions

What is the Lowest Common Ancestor in a Binary Tree?

The Lowest Common Ancestor of two nodes in a given binary tree is the lowest node that has both the given nodes as its descendants.

What are the applications of finding LCA in a Binary Tree?

There are many use cases of LCA in the programming; hence it becomes necessary to reduce the time complexity of this algorithm.

  • In Computer Graphics, we use the LCA algorithm to find the smallest cube among two given cubes.
  • In Object-oriented programming, we use LCA to find the most specialized superclass inherited by two different classes.
  • In the Compiler design, we find the lowest common ancestor of two basic blocks. The basic computation can be inserted into the ancestor, and it is available for both blocks.

What is the time complexity of binary lifting?

The worst-case, average-case, and best-case time complexities of the Binary Lifting approach for finding the LCA is O(logn), where n is the number of nodes in the Binary Tree.

The time complexity and the auxiliary space complexity of precomputing or preprocessing in binary lifting is O(n*logn).

Conclusion

Today we learned what the Lowest Ancestor Problem is and how to devise an efficient solution using the Binary Lifting Technique also explored the brute force methods for that problem.

Recommended Problems:

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Construct a Binary Tree from a given Preorder and Inorder Traversal
Next article
Construct a Complete Binary Tree from its Linked List Representation
Live masterclass