Nodes are on same path in a tree or Not

Problem Statement

Given a tree and two nodes of tree and the task to check whether these two nodes are on the same path from root to the bottom or not.

Example Input

Node1 = 1

Node2 = 5

Expected Output

Yes

Approach

The idea is to apply Depth First Search on every node. And traverse path from root to every leaf. If path contains the both node then return “Yes” otherwise return “No”.

Implementation in Python

def Depth_First_Search(Graph, v): 
	global Result1, Result2, Check_Visit, Limit, Count 
	Check_Visit[v] = True

	Count += 1

	Result1[v] = Count 
	it = 0
	while it < len(Graph[v]): 
		if (Check_Visit[Graph[v][it]] == False): 
			Depth_First_Search(Graph, Graph[v][it]) 
		it += 1

	Count += 1

	Result2[v] = Count 

def Check_Same_Path(u, v): 
	global Result1, Result2, Check_Visit, Limit, Count 
	return ((Result1[u] < Result1[v] and
			Result2[u] > Result2[v]) or
			(Result1[v] < Result1[u] and
			Result2[v] > Result2[u]) ) 

# Main Code
Limit = 100001

Check_Visit = [0] * Limit

Result1 = [0] * Limit
Result2 = [0] * Limit

Count = 0

n = 6 
Graph = [[] for i in range(n+1)] 
Graph[1].append(2) 
Graph[1].append(3) 
Graph[2].append(4) 
Graph[3].append(5) 
Graph[3].append(6) 

Depth_First_Search(Graph, 1) 

if Check_Same_Path(1, 5):
    print("Yes") 
else:
    print("No")