Distancia más corta entre dos Nodes en BST – Part 1

Dado un árbol de búsqueda binario y dos claves en él. Encuentre la distancia entre dos Nodes con dos claves dadas. Se puede suponer que ambas claves existen en BST.

Ejemplos:  

Input:  Root of above tree
         a = 3, b = 9
Output: 4
Distance between 3 and 9 in 
above BST is 4.

Input: Root of above tree
         a = 9, b = 25
Output: 3
Distance between 9 and 25 in 
above BST is 3.

Hemos discutido la distancia entre dos Nodes en el árbol binario . La complejidad temporal de esta solución es O(n)
En el caso de BST, podemos encontrar la distancia más rápido. Comenzamos desde la raíz y para cada Node, hacemos lo siguiente. 

1. Si ambas claves son mayores que el Node actual, nos movemos al hijo derecho del Node actual.
2. Si ambas claves son más pequeñas que el Node actual, nos movemos al elemento secundario izquierdo del Node actual.
3. Si una clave es menor y la otra clave es mayor, el Node actual es el ancestro común más bajo (LCA) de dos Nodes. Encontramos las distancias del Node actual a partir de dos claves y devolvemos la suma de las distancias.

Implementación:

// CPP program to find distance between
// two nodes in BST
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    struct Node* left, *right;
    int key;
};
 
struct Node* newNode(int key)
{
    struct Node* ptr = new Node;
    ptr->key = key;
    ptr->left = ptr->right = NULL;
    return ptr;
}
 
// Standard BST insert function
struct Node* insert(struct Node* root, int key)
{
    if (!root)
        root = newNode(key);
    else if (root->key > key)
        root->left = insert(root->left, key);
    else if (root->key < key)
        root->right = insert(root->right, key);
    return root;
}
 
// This function returns distance of x from
// root. This function assumes that x exists
// in BST and BST is not NULL.
int distanceFromRoot(struct Node* root, int x)
{
    if (root->key == x)
        return 0;
    else if (root->key > x)
        return 1 + distanceFromRoot(root->left, x);
    return 1 + distanceFromRoot(root->right, x);
}
 
// Returns minimum distance between a and b.
// This function assumes that a and b exist
// in BST.
int distanceBetween2(struct Node* root, int a, int b)
{
    if (!root)
        return 0;
 
    // Both keys lie in left
    if (root->key > a && root->key > b)
        return distanceBetween2(root->left, a, b);
 
    // Both keys lie in right
    if (root->key < a && root->key < b) // same path
        return distanceBetween2(root->right, a, b);
 
    // Lie in opposite directions (Root is
    // LCA of two nodes)
    if (root->key >= a && root->key <= b)
        return distanceFromRoot(root, a) +
               distanceFromRoot(root, b);
}
 
// This function make sure that a is smaller
// than b before making a call to findDistWrapper()
int findDistWrapper(Node *root, int a, int b)
{
   if (a > b)
     swap(a, b);
   return distanceBetween2(root, a, b);  
}
 
// Driver code
int main()
{
    struct Node* root = NULL;
    root = insert(root, 20);
    insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 30);
    insert(root, 25);
    insert(root, 35);
    int a = 5, b = 55;
    cout << findDistWrapper(root, 5, 35);
    return 0;
}

// Java program to find distance between
// two nodes in BST
class GfG {
 
static class Node {
    Node left, right;
    int key;
}
 
static Node newNode(int key)
{
    Node ptr = new Node();
    ptr.key = key;
    ptr.left = null;
    ptr.right = null;
    return ptr;
}
 
// Standard BST insert function
static Node insert(Node root, int key)
{
    if (root == null)
        root = newNode(key);
    else if (root.key > key)
        root.left = insert(root.left, key);
    else if (root.key < key)
        root.right = insert(root.right, key);
    return root;
}
 
// This function returns distance of x from
// root. This function assumes that x exists
// in BST and BST is not NULL.
static int distanceFromRoot(Node root, int x)
{
    if (root.key == x)
        return 0;
    else if (root.key > x)
        return 1 + distanceFromRoot(root.left, x);
    return 1 + distanceFromRoot(root.right, x);
}
 
// Returns minimum distance between a and b.
// This function assumes that a and b exist
// in BST.
static int distanceBetween2(Node root, int a, int b)
{
    if (root == null)
        return 0;
 
    // Both keys lie in left
    if (root.key > a && root.key > b)
        return distanceBetween2(root.left, a, b);
 
    // Both keys lie in right
    if (root.key < a && root.key < b) // same path
        return distanceBetween2(root.right, a, b);
 
    // Lie in opposite directions (Root is
    // LCA of two nodes)
    if (root.key >= a && root.key <= b)
        return distanceFromRoot(root, a) + distanceFromRoot(root, b);
         
    return 0;
}
 
// This function make sure that a is smaller
// than b before making a call to findDistWrapper()
static int findDistWrapper(Node root, int a, int b)
{
    int temp = 0;
if (a > b)
    {
    temp = a;
    a = b;
    b = temp;
    }
return distanceBetween2(root, a, b);
}
 
// Driver code
public static void main(String[] args)
{
    Node root = null;
    root = insert(root, 20);
    insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 30);
    insert(root, 25);
    insert(root, 35);
    System.out.println(findDistWrapper(root, 5, 35));
}
}

# Python3 program to find distance between
# two nodes in BST
class newNode:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.key = data
        self.left = None
        self.right = None
 
# Standard BST insert function
def insert(root, key):
    if root == None:
        root = newNode(key)
    else if root.key > key:
        root.left = insert(root.left, key)
    else if root.key < key:
        root.right = insert(root.right, key)
    return root
 
# This function returns distance of x from
# root. This function assumes that x exists
# in BST and BST is not NULL.
def distanceFromRoot(root, x):
    if root.key == x:
        return 0
    else if root.key > x:
        return 1 + distanceFromRoot(root.left, x)
    return 1 + distanceFromRoot(root.right, x)
 
# Returns minimum distance between a and b.
# This function assumes that a and b exist
# in BST.
def distanceBetween2(root, a, b):
    if root == None:
        return 0
 
    # Both keys lie in left
    if root.key > a and root.key > b:
        return distanceBetween2(root.left, a, b)
 
    # Both keys lie in right
    if root.key < a and root.key < b: # same path
        return distanceBetween2(root.right, a, b)
 
    # Lie in opposite directions
    # (Root is LCA of two nodes)
    if root.key >= a and root.key <= b:
        return (distanceFromRoot(root, a) +
                distanceFromRoot(root, b))
 
# This function make sure that a is smaller
# than b before making a call to findDistWrapper()
def findDistWrapper(root, a, b):
    if a > b:
        a, b = b, a
    return distanceBetween2(root, a, b)
 
# Driver code
if __name__ == '__main__':
    root = None
    root = insert(root, 20)
    insert(root, 10)
    insert(root, 5)
    insert(root, 15)
    insert(root, 30)
    insert(root, 25)
    insert(root, 35)
    a, b = 5, 55
    print(findDistWrapper(root, 5, 35))
 
# This code is contributed by PranchalK

// C# program to find distance between
// two nodes in BST
using System;
 
class GfG
{
 
public class Node
{
    public Node left, right;
    public int key;
}
 
static Node newNode(int key)
{
    Node ptr = new Node();
    ptr.key = key;
    ptr.left = null;
    ptr.right = null;
    return ptr;
}
 
// Standard BST insert function
static Node insert(Node root, int key)
{
    if (root == null)
        root = newNode(key);
    else if (root.key > key)
        root.left = insert(root.left, key);
    else if (root.key < key)
        root.right = insert(root.right, key);
    return root;
}
 
// This function returns distance of x from
// root. This function assumes that x exists
// in BST and BST is not NULL.
static int distanceFromRoot(Node root, int x)
{
    if (root.key == x)
        return 0;
    else if (root.key > x)
        return 1 + distanceFromRoot(root.left, x);
    return 1 + distanceFromRoot(root.right, x);
}
 
// Returns minimum distance between a and b.
// This function assumes that a and b exist
// in BST.
static int distanceBetween2(Node root, int a, int b)
{
    if (root == null)
        return 0;
 
    // Both keys lie in left
    if (root.key > a && root.key > b)
        return distanceBetween2(root.left, a, b);
 
    // Both keys lie in right
    if (root.key < a && root.key < b) // same path
        return distanceBetween2(root.right, a, b);
 
    // Lie in opposite directions (Root is
    // LCA of two nodes)
    if (root.key >= a && root.key <= b)
        return distanceFromRoot(root, a) +
                distanceFromRoot(root, b);
         
    return 0;
}
 
// This function make sure that a is smaller
// than b before making a call to findDistWrapper()
static int findDistWrapper(Node root, int a, int b)
{
    int temp = 0;
if (a > b)
    {
    temp = a;
    a = b;
    b = temp;
    }
return distanceBetween2(root, a, b);
}
 
// Driver code
public static void Main(String[] args)
{
    Node root = null;
    root = insert(root, 20);
    insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 30);
    insert(root, 25);
    insert(root, 35);
    Console.WriteLine(findDistWrapper(root, 5, 35));
}
}
 
// This code contributed by Rajput-Ji

<script>
 
// JavaScript program to find distance between
// two nodes in BST
 
     class Node {
            constructor() {
                this.key = 0;
                this.left = null;
                this.right = null;
            }
        }
 
    function newNode(key) {
var ptr = new Node();
        ptr.key = key;
        ptr.left = null;
        ptr.right = null;
        return ptr;
    }
 
    // Standard BST insert function
    function insert(root , key) {
        if (root == null)
            root = newNode(key);
        else if (root.key > key)
            root.left = insert(root.left, key);
        else if (root.key < key)
            root.right = insert(root.right, key);
        return root;
    }
 
    // This function returns distance of x from
    // root. This function assumes that x exists
    // in BST and BST is not NULL.
    function distanceFromRoot(root , x) {
        if (root.key == x)
            return 0;
        else if (root.key > x)
            return 1 + distanceFromRoot(root.left, x);
        return 1 + distanceFromRoot(root.right, x);
    }
 
    // Returns minimum distance between a and b.
    // This function assumes that a and b exist
    // in BST.
    function distanceBetween2(root , a , b) {
        if (root == null)
            return 0;
 
        // Both keys lie in left
        if (root.key > a && root.key > b)
            return distanceBetween2(root.left, a, b);
 
        // Both keys lie in right
        if (root.key < a && root.key < b) // same path
            return distanceBetween2(root.right, a, b);
 
        // Lie in opposite directions (Root is
        // LCA of two nodes)
        if (root.key >= a && root.key <= b)
            return distanceFromRoot(root, a) +
            distanceFromRoot(root, b);
 
        return 0;
    }
 
    // This function make sure that a is smaller
    // than b before making a call to findDistWrapper()
    function findDistWrapper(root , a , b) {
        var temp = 0;
        if (a > b) {
            temp = a;
            a = b;
            b = temp;
        }
        return distanceBetween2(root, a, b);
    }
 
    // Driver code
     
        var root = null;
        root = insert(root, 20);
        insert(root, 10);
        insert(root, 5);
        insert(root, 15);
        insert(root, 30);
        insert(root, 25);
        insert(root, 35);
        document.write(findDistWrapper(root, 5, 35));
 
// This code is contributed by todaysgaurav
 
</script>

4

Complejidad de tiempo: O(h) donde h es la altura del árbol de búsqueda binaria.

Este artículo es una contribución de Shweta Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.