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 parentvector<vector<int>> table;// Variable to store the height of the treeint height;// Graphvector<vector<int>> Graph;// Arrays to mark start and end time for a nodevector<int> timeIn, timeOut;// Timerint cnt_time;// constructor for initializing// the global variablesvoid 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 timevoid 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 Ancestorbool check(int u, int v){ return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];}// Function to return Lowest Common Ancestor of U and Vint 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 treebool 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 codeint 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 approachimport 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 approachimport mathn = 6# GraphGraph = []# log(n) with base 2height = 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 listsfor i in range(n + 1): Graph.append([])timeIn = [0]*(n + 1)timeOut = [0]*(n + 1)time = 0# Filling with -1 as initialdef 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 timedef 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 Ancestordef check(u, v): return (timeIn[u] <= timeIn[v] and timeOut[u] >= timeOut[v])# Function to return Lowest Common Ancestor of U and Vdef 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 treedef 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 graphpreprocessing(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, 2if isPresent(U, V, R): print("Yes")else: print("No") # This code is contributed by suresh07. |
C#
// C# implementation of the approachusing 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
