Check whether the given node is in the path between the nodes U and V

0 0 10 minutes read

Given three vertices U, V and R of a binary tree, the task is to check whether R lies in the path between U and V. If it is not present in the path then print No otherwise print Yes.
Examples:

Input: U = 4, V = 6, R = 2

Output: Yes
Path 4 -> 2 -> 1 -> 3 -> 6 contains 2
Input: U = 4, V = 6, R = 5

Output: No
Path 4 -> 2 -> 1 -> 3 -> 6 does not contain 5

Approach: The idea is to use Lowest Common Ancestor of two nodes. There are following cases for R to exist in the path between U and V:

R is the lowest common ancestor of U and V.
R is in the left subtree of the lowest common ancestor of U and V and is above V.
R is in the right subtree of the lowest common ancestor of U and V and is above U.

To know more about the lowest common ancestor, read the post here.
Below is the implementation of the above approach:

C++

// CPP Program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Table for storing 2^ith parent
vector<vector<int>> table;
 
// Variable to store the height of the tree
int height;
 
// Graph
vector<vector<int>> Graph;
 
// Arrays to mark start and end time for a node
vector<int> timeIn, timeOut;
 
// Timer
int cnt_time;
 
// constructor for initializing
// the global variables
void initialise(int n)
{
 
  // log(n) with base 2
  height = (int)ceil(log2(n));
 
  // Filling with -1 as initial
  table.resize(n + 1, vector<int>(height + 1, -1));
 
  // Fill the graph with empty lists
  Graph.resize(n + 1);
  timeIn.resize(n + 1);
  timeOut.resize(n + 1);
  cnt_time = 0;
}
 
// Dfs for pre-processing sparse table and
// calculating start and end time
void dfs(int s, int p)
{
 
  // Parent at 1 node distance is always
  // it's direct parent
  table[s][0] = p;
 
  // Start time noted
  timeIn[s] = ++cnt_time;
 
  // Filling sparse table recursively
  for (int i = 1; i <= height; i++)
    table[s][i] = table[table[s][i - 1]][i - 1];
 
  // Traversing children of source
  for (int child : Graph[s]) {
    if (child == p) continue;
    dfs(child, s);
  }
 
  // End time noted
  timeOut[s] = ++cnt_time;
}
 
// Helper function to check lowest common Ancestor
bool check(int u, int v)
{
  return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
}
 
// Function to return Lowest Common Ancestor of U and V
int lowestCommonAncestor(int U, int V)
{
  if (check(U, V)) return U;
 
  if (check(V, U)) return V;
 
  for (int i = height; i >= 0; i--)
  {
    if (!check(table[U][i], V)) U = table[U][i];
  }
 
  return table[U][0];
}
 
// Function that return true if R
// exists on the path between U
// and V in the given tree
bool isPresent(int U, int V, int R) 
{
 
  // Dfs
  dfs(1, 1);
 
  // Calculating LCA between U and V
  int LCA = lowestCommonAncestor(U, V);
 
  // Calculating LCA between U and R
  int LCA_1 = lowestCommonAncestor(U, R);
 
  // Calculating LCA between U and V
  int LCA_2 = lowestCommonAncestor(V, R);
 
  if (LCA == R || (LCA_1 == LCA && LCA_2 == R) ||
      (LCA_2 == LCA && LCA_1 == R)) {
    return true;
  }
  return false;
}
 
// Driver code
int main(int argc, char const *argv[]) 
{
 
  // Number of vertices
  int n = 6;
  initialise(n);
 
  // Create the graph
  Graph[1].push_back(2);
  Graph[2].push_back(1);
  Graph[1].push_back(3);
  Graph[3].push_back(1);
  Graph[2].push_back(4);
  Graph[4].push_back(2);
  Graph[2].push_back(5);
  Graph[5].push_back(2);
  Graph[3].push_back(6);
  Graph[6].push_back(3);
 
  int U = 4, V = 6, R = 2;
  if (isPresent(U, V, R))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
 
// This code is contributed by sanjeev2552

Java

// Java implementation of the approach
import java.util.*;
 
class GfG {
 
    // Table for storing 2^ith parent
    private static int table[][];
 
    // Variable to store the height of the tree
    private static int height;
 
    // Graph
    private static ArrayList<ArrayList<Integer> > Graph;
 
    // Arrays to mark start and end time for a node
    private static int timeIn[];
    private static int timeOut[];
 
    // Timer
    private static int time;
 
    // Private constructor for initializing
    // the global variables
    private GfG(int n)
    {
 
        // log(n) with base 2
        height = (int)Math.ceil(Math.log10(n) / Math.log10(2));
        table = new int[n + 1][height + 1];
 
        // Fill the graph with empty lists
        Graph = new ArrayList<ArrayList<Integer> >();
        for (int i = 0; i <= n; i++)
            Graph.add(new ArrayList<Integer>());
        timeIn = new int[n + 1];
        timeOut = new int[n + 1];
        time = 0;
    }
 
    // Filling with -1 as initial
    private static void preprocessing(int n)
    {
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(table[i], -1);
        }
    }
 
    // Dfs for pre-processing sparse table and
    // calculating start and end time
    private static void dfs(int s, int p)
    {
        // Parent at 1 node distance is always
        // it's direct parent
        table[s][0] = p;
 
        // Start time noted
        timeIn[s] = ++time;
 
        // Filling sparse table recursively
        for (int i = 1; i <= height; i++)
            table[s][i] = table[table[s][i - 1]][i - 1];
 
        // Traversing children of source
        for (int child : Graph.get(s)) {
            if (child == p)
                continue;
            dfs(child, s);
        }
 
        // End time noted
        timeOut[s] = ++time;
    }
 
    // Helper function to check lowest common Ancestor
    private static boolean check(int u, int v)
    {
        return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
    }
 
    // Function to return Lowest Common Ancestor of U and V
    private static int lowestCommonAncestor(int U, int V)
    {
        if (check(U, V))
            return U;
 
        if (check(V, U))
            return V;
 
        for (int i = height; i >= 0; i--) {
            if (!check(table[U][i], V))
                U = table[U][i];
        }
 
        return table[U][0];
    }
 
    // Function that return true if R
    // exists on the path between U
    // and V in the given tree
    private static boolean isPresent(int U, int V, int R)
    {
 
        // Dfs
        dfs(1, 1);
 
        // Calculating LCA between U and V
        int LCA = lowestCommonAncestor(U, V);
 
        // Calculating LCA between U and R
        int LCA_1 = lowestCommonAncestor(U, R);
 
        // Calculating LCA between U and V
        int LCA_2 = lowestCommonAncestor(V, R);
 
        if (LCA == R || (LCA_1 == LCA && LCA_2 == R)
            || (LCA_2 == LCA && LCA_1 == R)) {
            return true;
        }
        return false;
    }
 
    // Driver code
    public static void main(String args[])
    {
        // Number of vertices
        int n = 6;
        GfG obj = new GfG(n);
 
        // Create the graph
        preprocessing(n);
        Graph.get(1).add(2);
        Graph.get(2).add(1);
        Graph.get(1).add(3);
        Graph.get(3).add(1);
        Graph.get(2).add(4);
        Graph.get(4).add(2);
        Graph.get(2).add(5);
        Graph.get(5).add(2);
        Graph.get(3).add(6);
        Graph.get(6).add(3);
 
        int U = 4, V = 6, R = 2;
        if (isPresent(U, V, R))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}

Python3

# Python3 implementation of the approach
import math
 
n = 6
 
# Graph
Graph = []
 
# log(n) with base 2
height = math.ceil(math.log10(n) / math.log10(2))
table = [[-1 for i in range(n + 1)] for j in range(n + 1)]
 
# Fill the graph with empty lists
for i in range(n + 1):
  Graph.append([])
timeIn = [0]*(n + 1)
timeOut = [0]*(n + 1)
time = 0
 
# Filling with -1 as initial
def preprocessing(n):
    for i in range(n + 1):
        for j in range(height + 1):
            table[i][j] = -1
 
# Dfs for pre-processing sparse table and
# calculating start and end time
def dfs(s, p):
    global time
    # Parent at 1 node distance is always
    # it's direct parent
    table[s][0] = p
     
    # Start time noted
    timeIn[s] = time+1
 
    # Filling sparse table recursively
    for i in range(1, height + 1):
        table[s][i] = table[table[s][i - 1]][i - 1]
 
    # Traversing children of source
    for child in range(len(Graph[s])):
        if Graph[s][child] == p:
            continue
        dfs(Graph[s][child], s)
 
    # End time noted
    time+=1
    timeOut[s] = time
 
# Helper function to check lowest common Ancestor
def check(u, v):
    return (timeIn[u] <= timeIn[v] and timeOut[u] >= timeOut[v])
 
# Function to return Lowest Common Ancestor of U and V
def lowestCommonAncestor(U, V):
    if check(U, V):
        return U
 
    if check(V, U):
        return V
 
    for i in range(height, -1, -1):
        if not check(table[U][i], V):
            U = table[U][i]
 
    return table[U][0]
 
# Function that return true if R
# exists on the path between U
# and V in the given tree
def isPresent(U, V, R):
    # Dfs
    dfs(1, 1)
 
    # Calculating LCA between U and V
    LCA = lowestCommonAncestor(U, V)
 
    # Calculating LCA between U and R
    LCA_1 = lowestCommonAncestor(U, R)
 
    # Calculating LCA between U and V
    LCA_2 = lowestCommonAncestor(V, R)
 
    if LCA == R or (LCA_1 == LCA and LCA_2 == R) or (LCA_2 == LCA and LCA_1 == R):
        return True
    return False
 
# Create the graph
preprocessing(n)
Graph[1].append(2)
Graph[2].append(1)
Graph[1].append(3)
Graph[3].append(1)
Graph[2].append(4)
Graph[4].append(2)
Graph[2].append(5)
Graph[5].append(2)
Graph[3].append(6)
Graph[6].append(3)
 
U, V, R = 4, 6, 2
if isPresent(U, V, R):
  print("Yes")
else:
  print("No")
   
  # This code is contributed by suresh07.

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GfG 
{
 
    // Table for storing 2^ith parent
    private static int [,]table;
 
    // Variable to store the height of the tree
    private static int height;
 
    // Graph
    private static List<List<int> > Graph;
 
    // Arrays to mark start and end time for a node
    private static int []timeIn;
    private static int []timeOut;
 
    // Timer
    private static int time;
 
    // Private constructor for initializing
    // the global variables
    private GfG(int n)
    {
 
        // log(n) with base 2
        height = (int)Math.Ceiling(Math.Log10(n) / Math.Log10(2));
        table = new int[n + 1, height + 1];
 
        // Fill the graph with empty lists
        Graph = new List<List<int> >();
        for (int i = 0; i <= n; i++)
            Graph.Add(new List<int>());
        timeIn = new int[n + 1];
        timeOut = new int[n + 1];
        time = 0;
    }
 
    // Filling with -1 as initial
    private static void preprocessing(int n)
    {
        for (int i = 0; i < n + 1; i++) 
        {
            for(int j = 0; j < height + 1; j++)
                table[i, j] = -1;
        }
    }
 
    // Dfs for pre-processing sparse table and
    // calculating start and end time
    private static void dfs(int s, int p)
    {
        // Parent at 1 node distance is always
        // it's direct parent
        table[s, 0] = p;
 
        // Start time noted
        timeIn[s] = ++time;
 
        // Filling sparse table recursively
        for (int i = 1; i <= height; i++)
            table[s, i] = table[table[s, i - 1], i - 1];
 
        // Traversing children of source
        foreach (int child in Graph[s])
        {
            if (child == p)
                continue;
            dfs(child, s);
        }
 
        // End time noted
        timeOut[s] = ++time;
    }
 
    // Helper function to check lowest common Ancestor
    private static bool check(int u, int v)
    {
        return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
    }
 
    // Function to return Lowest Common Ancestor of U and V
    private static int lowestCommonAncestor(int U, int V)
    {
        if (check(U, V))
            return U;
 
        if (check(V, U))
            return V;
 
        for (int i = height; i >= 0; i--) 
        {
            if (!check(table[U, i], V))
                U = table[U, i];
        }
 
        return table[U, 0];
    }
 
    // Function that return true if R
    // exists on the path between U
    // and V in the given tree
    private static bool isPresent(int U, int V, int R)
    {
 
        // Dfs
        dfs(1, 1);
 
        // Calculating LCA between U and V
        int LCA = lowestCommonAncestor(U, V);
 
        // Calculating LCA between U and R
        int LCA_1 = lowestCommonAncestor(U, R);
 
        // Calculating LCA between U and V
        int LCA_2 = lowestCommonAncestor(V, R);
 
        if (LCA == R || (LCA_1 == LCA && LCA_2 == R)
            || (LCA_2 == LCA && LCA_1 == R)) 
        {
            return true;
        }
        return false;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        // Number of vertices
        int n = 6;
        GfG obj = new GfG(n);
 
        // Create the graph
        preprocessing(n);
        Graph[1].Add(2);
        Graph[2].Add(1);
        Graph[1].Add(3);
        Graph[3].Add(1);
        Graph[2].Add(4);
        Graph[4].Add(2);
        Graph[2].Add(5);
        Graph[5].Add(2);
        Graph[3].Add(6);
        Graph[6].Add(3);
 
        int U = 4, V = 6, R = 2;
        if (isPresent(U, V, R))
            Console.Write("Yes");
        else
            Console.Write("No");
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
    // JavaScript implementation of the approach
     
    let n = 6;
     
    // Table for storing 2^ith parent
    let table;
  
    // Variable to store the height of the tree
    let height;
  
    // Graph
    let Graph = [];
  
    // Arrays to mark start and end time for a node
    let timeIn;
    let timeOut;
  
    // Timer
    let time;
  
  
    // log(n) with base 2
    height = Math.ceil(Math.log10(n) / Math.log10(2));
    table = new Array(n + 1);
 
    // Fill the graph with empty lists
    for (let i = 0; i <= n; i++)
      Graph.push([]);
    timeIn = new Array(n + 1);
    timeOut = new Array(n + 1);
    time = 0;
  
    // Filling with -1 as initial
    function preprocessing(n)
    {
        for (let i = 0; i < n + 1; i++) {
            table[i] = new Array(height + 1);
            for(let j = 0; j < height + 1; j++)
            {
                table[i][j] = -1;
            }
        }
    }
  
    // Dfs for pre-processing sparse table and
    // calculating start and end time
    function dfs(s, p)
    {
        // Parent at 1 node distance is always
        // it's direct parent
        table[s][0] = p;
  
        // Start time noted
        timeIn[s] = ++time;
  
        // Filling sparse table recursively
        for (let i = 1; i <= height; i++)
            table[s][i] = table[table[s][i - 1]][i - 1];
  
        // Traversing children of source
        for (let child = 0; child < Graph[s].length; child++) {
            if (Graph[s][child] == p)
                continue;
            dfs(Graph[s][child], s);
        }
  
        // End time noted
        timeOut[s] = ++time;
    }
  
    // Helper function to check lowest common Ancestor
    function check(u, v)
    {
        return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
    }
  
    // Function to return Lowest Common Ancestor of U and V
    function lowestCommonAncestor(U, V)
    {
        if (check(U, V))
            return U;
  
        if (check(V, U))
            return V;
  
        for (let i = height; i >= 0; i--) {
            if (!check(table[U][i], V))
                U = table[U][i];
        }
  
        return table[U][0];
    }
  
    // Function that return true if R
    // exists on the path between U
    // and V in the given tree
    function isPresent(U, V, R)
    {
  
        // Dfs
        dfs(1, 1);
  
        // Calculating LCA between U and V
        let LCA = lowestCommonAncestor(U, V);
  
        // Calculating LCA between U and R
        let LCA_1 = lowestCommonAncestor(U, R);
  
        // Calculating LCA between U and V
        let LCA_2 = lowestCommonAncestor(V, R);
  
        if (LCA == R || (LCA_1 == LCA && LCA_2 == R)
            || (LCA_2 == LCA && LCA_1 == R)) {
            return true;
        }
        return false;
    }
 
    // Create the graph
    preprocessing(n);
    Graph[1].push(2);
    Graph[2].push(1);
    Graph[1].push(3);
    Graph[3].push(1);
    Graph[2].push(4);
    Graph[4].push(2);
    Graph[2].push(5);
    Graph[5].push(2);
    Graph[3].push(6);
    Graph[6].push(3);
 
    let U = 4, V = 6, R = 2;
    if (isPresent(U, V, R))
      document.write("Yes");
    else
      document.write("No");
 
</script>

Output:

Yes

Time Complexity: O(NlogN) for pre-processing and logN for finding the lowest common ancestor.
Auxiliary Space: O(NlogN).

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!