Binary Search Trees: Get the Shortest distance between two nodes in BST

Problem Statement:

You are given the root node of BST and 2 key elements.

You need to find the distance between the 2 nodes.

Solution

So as the tree is a BST, if both the keys are greater than the current node, then move right else move to left child.

Then if one key is smaller and other is greater, then the current node is LCA of the 2 nodes.

Then we find the distances of current node from two keys and return the sum of distances.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int data) 
{ 
    if (node == NULL) return get_new_node(data); 
  
    if (data < node->data) 
        node->left  = insert_into_bst(node->left, data); 
    else if (data > node->data) 
        node->right = insert_into_bst(node->right, data);    
  
    return node; 
} 

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 

int distance_from_root(struct Node* root, int x)
{
    if (root->data == x)
        return 0;
    else if (root->data > x)
        return 1 + distance_from_root(root->left, x);
    return 1 + distance_from_root(root->right, x);
}
  
int distance_between_two_values(struct Node* root, int a, int b)
{
    if (!root)
        return 0;
  
    // go left
    if (root->data > a && root->data > b)
        return distance_between_two_values(root->left, a, b);
  
    // go right
    if (root->data < a && root->data < b) 
        return distance_between_two_values(root->right, a, b);
  
    if (root->data >= a && root->data <= b)
        return distance_from_root(root, a) + 
               distance_from_root(root, b);
}

int main()
{
    Node *root_1 = NULL; 
    root_1 = insert_into_bst(root_1, 1); 
    insert_into_bst(root_1, 2); 
    insert_into_bst(root_1, 3); 
    insert_into_bst(root_1, 4); 
    insert_into_bst(root_1, 5); 

    cout<<"The shortest distance between 4 and 5 is "<<distance_between_two_values(root_1, 4, 5)<<endl;

    return 0;
}

Output:

The shortest distance between 4 and 5 is 1