# 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.

Node1 = 1

Node2 = 5

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 =  * Limit

Result1 =  * Limit
Result2 =  * Limit

Count = 0

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

Depth_First_Search(Graph, 1)

if Check_Same_Path(1, 5):
print("Yes")
else:
print("No")```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]