forked from imsushant12/GFG-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Min_distance_between_two_given_nodes_of_a_Binary_Tree.cpp
97 lines (77 loc) · 2.49 KB
/
Min_distance_between_two_given_nodes_of_a_Binary_Tree.cpp
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
/*
Problem Statement:
-----------------
Given a binary tree and two node values your task is to find the minimum distance between them.
Example 1:
---------
Input:
1
/ \
2 3
a = 2, b = 3
Output: 2
Explanation: The tree formed is:
1
/ \
2 3
We need the distance between 2 and 3. Being at node 2, we need to take two steps ahead in order to reach node 3. The path followed will be:
2 -> 1 -> 3. Hence, the result is 2.
Your Task: You don't need to read input or print anything. Your task is to complete the function findDist() which takes the root node of the Tree
and the two node values a and b as input parameters and returns the minimum distance between the nodes represented by the two given node values.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 104
1 <= Data of a node <= 105
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only.
As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.
*/
// Link --> https://practice.geeksforgeeks.org/problems/min-distance-between-two-given-nodes-of-a-binary-tree/1
// Code:
int findLevel(Node *root, int k, int level)
{
if (root == NULL)
return -1;
if (root->data == k)
return level;
int l = findLevel(root->left, k, level + 1);
return (l != -1) ? l : findLevel(root->right, k, level + 1);
}
Node *findDistU(Node *root , int n1 , int n2 , int &d1 , int &d2 , int &dist , int lvl)
{
if (root == NULL)
return NULL;
if (root->data == n1)
{
d1 = lvl;
return root;
}
if (root->data == n2)
{
d2 = lvl;
return root;
}
Node *l = findDistU(root->left , n1 , n2 , d1 , d2 , dist , lvl+1);
Node *r = findDistU(root->right , n1 , n2 , d1 , d2 , dist , lvl+1);
if (l and r)
dist = d1 + d2 - 2 * lvl;
return (l != NULL) ? l : r;
}
int findDist(Node *root, int n1, int n2)
{
int d1 = -1, d2 = -1, dist;
Node *lca = findDistU(root, n1, n2, d1, d2, dist, 1);
if (d1 != -1 and d2 != -1)
return dist;
if (d1 != -1)
{
dist = findLevel(lca, n2, 0);
return dist;
}
if (d2 != -1)
{
dist = findLevel(lca, n1, 0);
return dist;
}
return -1;
}