#include <bits/stdc++.h>
using namespace std;
// tree node is defined
class TreeNode
{
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
val = data;
left = NULL;
right = NULL;
}
};
// distance b/w a node and the root of the subtree
int findDistance(TreeNode *root, int v)
{
int dist = 0;
TreeNode *cur = root;
while (cur)
{
if (cur->val == v)
return dist;
else
{
dist++;
if (cur->val > v)
cur = cur->left;
else
cur = cur->right;
}
}
return 0;
}
// function that finds distance b/w two nodes in a BST
int distanceBWNodes(TreeNode *root, int v1, int v2)
{
// null tree
if (!root)
return 0;
// same node
if (v1 == v2)
return 0;
if (root->val < v1 && root->val < v2)
{
return distanceBWNodes(root->right, v1, v2);
}
else if (root->val > v1 && root->val > v2)
{
return distanceBWNodes(root->left, v1, v2);
}
else
{
return findDistance(root, v1) + findDistance(root, v2);
}
}
int main()
{
TreeNode *root = new TreeNode(20);
root->left = new TreeNode(18);
root->right = new TreeNode(28);
root->left->left = new TreeNode(15);
root->left->right = new TreeNode(19);
root->right->left = new TreeNode(23);
root->right->right = new TreeNode(34);
root->left->left->left = new TreeNode(11);
root->left->left->right = new TreeNode(16);
root->left->left->right->right = new TreeNode(17);
root->right->left->left = new TreeNode(21);
cout << "Distances B/w nodes 16 & 17 is: " << distanceBWNodes(root, 16, 17) << endl;
cout << "Distances B/w nodes 16 & 28 is: " << distanceBWNodes(root, 16, 28) << endl;
return 0;
}
Output
Distances B/w nodes 16 & 17 is: 1
Distances B/w nodes 16 & 28 is: 4
0 Comments