Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
What is a Binary Tree?
1.2.
Problem Statement
1.3.
Sample Examples
2.
Approach
2.1.
PseudoCode
2.2.
Implementation in Java
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
Give some real-life applications where we use tree data structure.
3.2.
What is Traversal? What are the three types of tree traversal techniques?
3.3.
Mention some disadvantages of Tree.
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Lowest Common Ancestor in Binary Tree using RMQ

Author Rupal Saluja
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will try to understand a very interesting problem of a Binary Tree data structure in which we will find the Lowest Common Ancestor of any two given nodes of that binary tree using RMQ. Through that problem, we will learn how to approach any such problem. Firstly, we will look into the problem statement, get some knowledge about Binary tree data structure, decide what will be the optimal approach, and then we will proceed towards the implementation in any of the programming languages.

What is a Binary Tree?

A Binary Tree is a type of tree data structure in which elements have the utmost two children nodes. Since, in this data structure, elements have only two children nodes, we name them the left child and the right child.

Any node of Binary contains the following information. These are:

  1. Its data
  2. Pointer to its left child.
  3. Pointer to its right child.

For Example, if we consider the tree above, 10 is the root node, and the rest of the nodes are its children nodes. We pick any node, say 6, so, 5 will be its left child and 19 will be its right child. That is, 6 is the parent node to children nodes 5 and 19.

Problem Statement

Firstly, we will have a look at what exactly the problem says. 

We are given a binary tree that has n nodes. We have to find the lowest common ancestor of any two given nodes of that binary tree using RMQ. By lowest common ancestor, we mean that parent node which is the lowest and is common to both of the given nodes.

RMQ stands for Range Minimum Query. RMQ is used to find out the position of the element whose value is minimum between the two mentioned indices. There are three approaches for solving RMQ, namely, Brute force, Square Root Decomposition, and Segment Tree Approach with different time and space complexities. Since we find that the Segment Tree Approach is the most optimal one, we will use that approach here.

Here, we are assuming that all the values inside the nodes are positive.

Sample Examples

Let us understand the above-mentioned concepts, which are, Lowest Common Ancestor and Range Minimum Query with the help of examples.

Suppose that we have a binary tree as you can see in the image below. We have to search for the lowest common ancestor of the two given nodes of that binary tree. We will use the same binary tree for different examples to have a better grab of all the possible cases.

Example 1:

Explanation:

In the above example, we can see a binary tree. Firstly, we will search for both the input nodes, which are, 5 and 9. As soon as we get the nodes, we will traverse up to find all the ancestors of both the nodes and then determine which one is common to both and the lowest. Now, that be can see that 5 and 19 are children of the same node with value 6, and also, both the input nodes are at the same level. In this case, the output will be 6.

Example 2:

Explanation:

In the above example, we can see a binary tree. Firstly, we will search for both the input nodes, which are 5 and 24. As soon as we get the nodes, we will traverse up to find all the ancestors of both the nodes and then determine which one is common to both and the lowest. Now, that be can see that 5 and 24 appear on the right side of the root node but are at different levels. The lowest common ancestor we observe in this case is 24.

Example 3:

Explanation:

In the above example, we can see a binary tree. Firstly, we will search for both the input nodes, which are 18 and 24. As soon as we get the nodes, we will traverse up to find all the ancestors of both the nodes and then determine which one is common to both and the lowest. Now, that be can see that 18 and 24 appear at the different sides of the root node and also are at different levels. The lowest common ancestor we observe in this case is the root node itself, that is, 10.

Approach

For this problem, firstly, our approach is to traverse the tree using Euler’s tour method.

We will use two arrays also. The first array will be used to store the nodes coming in the path while traversing and the second node will be used to store their corresponding levels.

Euler’s Path:

Corresponding levels:

 As soon as we get the input two nodes for which we need to find the lowest common ancestor, we will search them in the first array and mark their first occurrence. Let's say we took 15 and 6 as the input nodes.

Now we will mark the same indices in the second array.

We observe that there are three elements between the two marked boxes, that is, 2, 3, and 0. The smallest of all three is 0. Now, that we know 0 is the smallest corresponding level. We will refer to the first array and find what value exists corresponding to 0, that is 10. So, the output will be 10.

PseudoCode

//Function to find Lowest Common Ancestor
int searchLCA(TreeNode node, int n1, int n2)
{
    Arrays.fill(first, -1);
    entry = 0;
    Tour(parent, 0);
    obj.segment_tree = constructST(cl, 2 * n2 - 1);
    if (first[n1] > first[n2])
        n1 = swapping(n1, n1 = n2);
    int a = first[n1];
    int b = first[n2];
    int index = RMQ(obj, 2 * n2 - 1, a, b);
    return euler_path[index];
}

Implementation in Java

import java.util.*;
class Segment
{
    int segment_tree;
    int segment_array[] = new int[1000];
}
class TreeNode
{
    TreeNode l, r;
    int value;
  
    TreeNode(int number)
    {
        value= number;
        l = r = null;
    }
}
class Main
{
    TreeNode parent;
    int n2 = 9; // v is the highest value of node in our tree
    int euler_path[] = new int[2 * n2 - 1];
    int cl[] = new int[2 * n2 - 1]; 
    int first[] = new int[2 * n2 - 1];
    int entry;
    Segment obj = new Segment();
    
    // Driver program
    public static void main(String args[])
    {
        Main tree = new Main();
        tree.parent = new TreeNode(8);
        tree.parent.l = new TreeNode(2);
        tree.parent.r = new TreeNode(5);
        tree.parent.l.l = new TreeNode(4);
        tree.parent.l.r = new TreeNode(6);
        tree.parent.r.l = new TreeNode(9);
        tree.parent.r.r = new TreeNode(7);
        tree.parent.l.r.l = new TreeNode(1);
        tree.parent.l.r.r = new TreeNode(3);
  
        int n1 = 4, n2 = 9;
        System.out.println(tree.searchLCA(tree.parent, n1, n2));
    }
  
    int swapping(int val1, int val2)    
    {
        return val1;
    }
    
    int Log2(int num1)
    {
        int result = 0;
        int num2 = num1 >>= 1;
        while (num2-- != 0)
            result++;
        return result;
    }
    
    // Euler Path of Tree
    void Tour(TreeNode node, int l)
    {
        if (node != null)
        {
            euler_path[entry] = node.value;
            cl[entry] = l; 
            entry++;
            if (first[node.value] == -1)
                first[node.value] = entry - 1;
            if (node.l != null)
            {
                Tour(node.l, l + 1);
                euler_path[entry] = node.value;
                cl[entry] = l;
                entry++;
            }
            if (node.r != null)
            {
                Tour(node.r, l + 1);
                euler_path[entry] = node.value;
                cl[entry] = l;
                entry++;
            }
        }
    }
  
    
    //To construct segment tree
    int constructST(int array[], int n)
    {
        int x = Log2(n) + 1;
        int max_size = 2 * (1 << x) - 1;
        obj.segment_array = new int[max_size];
        make_segment(0, 0, n - 1, array, obj);
        return obj.segment_tree;
    }
  
    //Function to implement RMQ
    int RMQ(int position, int s1, int s2, int a, int b, Segment segment_tree)
    {
        //conditions for RMQ
        if (a <= s1 && b >= s2)
            return segment_tree.segment_array[position];
        else if (s2 < a || s1 > b)
            return -1;
        int middle = (s1 + s2) / 2;
  
        int c = RMQ(2 * position + 1, s1, middle, a, b, segment_tree);
        int d = RMQ(2 * position + 2, middle + 1, s2, a, b, segment_tree);
  
        if (c == -1)
            return d;
        else if (d == -1)
            return c;
  
        return (cl[c] < cl[d]) ? c : d;
    }
  
    // Uses RMQ function to return minimum of elements between indices a and b
    int RMQ(Segment segment_tree, int n, int a, int b)
    {
        if (a < 0 || b > n - 1 || a > b)
        {
            System.out.println("Invalid input");
            return -1;
        }
  
        return RMQ(0, 0, n - 1, a, b, segment_tree);
    }
  
    //Recursive function to construct Segment Tree
    void make_segment(int si, int s1, int s2, int arr[], Segment segment_tree)
    {
        if (s1 == s2)
            segment_tree.segment_array[si] = s1;
        else
        {
            int middle = (s1 + s2) / 2;
            make_segment(si * 2 + 1, s1, middle, arr, segment_tree);
            make_segment(si * 2 + 2, middle + 1, s2, arr, segment_tree);
  
            if (arr[segment_tree.segment_array[2 * si + 1]] < arr[segment_tree.segment_array[2 * si + 2]])
                segment_tree.segment_array[si] = segment_tree.segment_array[2 * si + 1];
            else
                segment_tree.segment_array[si] = segment_tree.segment_array[2 * si + 2];
        }
    }
  
    //Function to find Lowest Common Ancestor
    int searchLCA(TreeNode node, int n1, int n2)
    {
        Arrays.fill(first, -1);
        entry = 0;
        Tour(parent, 0);
        obj.segment_tree = constructST(cl, 2 * n2 - 1);
        if (first[n1] > first[n2])
            n1 = swapping(n1, n1 = n2);
        int a = first[n1];
        int b = first[n2];
        int index = RMQ(obj, 2 * n2 - 1, a, b);
        return euler_path[index];
    }
}

 

Input: 

n1=4, n2=9

 

Output: 

8

 

Complexity Analysis

Time Complexity

  • For Euler’s path, if the number of nodes is ‘n’. Then, the resultant complexity will be O(n).
  • For the construction of the Segment Tree, the complexity will be O(n).
  • For RMQ, the complexity will be O(log n).

 

So, we conclude that the overall complexity for the implementation above is O(log n).

 

Space Complexity

We observe that extra auxiliary space is required in various instances. Hence, the resultant space complexity will be O(n).

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

Frequently Asked Questions

Give some real-life applications where we use tree data structure.

Some real-life examples of the tree data structure are given below.

  • It is used to store hierarchical data
  • In organization charts of large firms.
  • Machine learning Algorithms.
  • Computer Graphics
  • Java Virtual Machine
  • In servers like DNS


What is Traversal? What are the three types of tree traversal techniques?

When we use tree data structure, there is always a way in which we perform certain operations like searching a node, finding the depth and height of the tree, sorting, deleting, etc. The way in which every node is reached determines the type of traversal that tree is using

The three types of tree traversal techniques are explained below.

  • Inorder Traversal
  • Preorder Traversal
  • Postorder Traversal

 

Mention some disadvantages of Tree.

Some prominent disadvantages of the Tree Data Structure are listed below.

  • Hard to implement
  • Programming Complexity
  • Difficulty in Database Management
  • Expensive for small applications

Conclusion

Through this blog, we tried to explain to you the concepts of Binary Tree and RMQ using a problem. We had a look at every possible condition that could occur, understood the approach, went through the Pseudocode, saw the implementation, tested the code against an example input, and analyzed the time and space complexities.

We hope the above discussion helped you understand and solve the problem better.

This will also help you learn how to approach any problem like this in the future.
For coders out there who want to solve more such questions, refer to the list below.

 

Make sure that you enroll in the courses provided by us, take mock tests and solve problems available and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help fellow ninjas grow.

Happy Coding!

Previous article
Print Ancestors of a Given Node
Next article
Print longest leaf to leaf paths in a binary tree
Live masterclass