-
Notifications
You must be signed in to change notification settings - Fork 506
Expand file tree
/
Copy pathMinimumDistanceBetweenNodeGT.cpp
More file actions
98 lines (72 loc) Β· 1.9 KB
/
MinimumDistanceBetweenNodeGT.cpp
File metadata and controls
98 lines (72 loc) Β· 1.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
// https://www.geeksforgeeks.org/minimum-distance-between-two-given-nodes-in-an-n-ary-tree/
// defining node
class node{
public:
int data;
vector<node*> children;
node(int val){
this->data=val;
}
};
void creatingtree(node* &root,int arr[],int n){
stack<node*> st;
for(int i=0;i<n;i++){
if(arr[i]==-1){
st.pop();
}
else{
node* newnode= new node(arr[i]);
if(st.size()>0){
st.top()->children.push_back(newnode);
}
else{
root=newnode;
}
st.push(newnode);
}
}
}
vector<int> nodetopath(node* root,int k){
//if n=root itself a data
if(root->data==k){
vector<int>baseresult;
baseresult.push_back(root->data);
return baseresult;
}
// if data !=root therefor call for children
for(node* child:root->children){
vector<int>pathtillchildren=nodetopath(child,k);
if(pathtillchildren.size()>0){ //it means the required data must be present here
pathtillchildren.push_back(root->data);
return pathtillchildren;
}
}
// if we come out of this for looop means no data is found hence we have to return empty list
vector<int> emptylist;
return emptylist;
}
int distancebetwennode(node* root,int k1,int k2){
vector<int>p1=nodetopath(root,k1);
vector<int>p2=nodetopath(root,k2);
int i=p1.size()-1;
int j=p2.size()-1;
while(i>=0 && j>=0 && p1[i]== p2[j] ){
i--;
j--;
}
i++;
j++;
return i+j;
}
int main(){
node* root=NULL;
int arr[]={10,20,50,-1,60,-1,-1,30,70,-1,80,110,-1,120,-1,-1,90,-1,-1,40,100,-1,-1,-1};
int n=sizeof(arr)/sizeof(arr[0]);
creatingtree(root,arr,n);
int k1=100;
int k2=110;
int f=distancebetwennode(root,k1,k2);
cout<<"minimum distance between two node: "<<f;
}