Encuentre la distancia desde la raíz hasta el Node dado en un árbol binario

Dada la raíz de un árbol binario y una clave x en él, encuentre la distancia de la clave dada desde la raíz. Distancia significa el número de aristas entre dos Nodes.

Ejemplos: 

C++

// C++ program to find distance of a given
// node from root.
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node
{
    int data;
    Node *left, *right;
};
 
// A utility function to create a new Binary
// Tree Node
Node *newNode(int item)
{
    Node *temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Returns -1 if x doesn't exist in tree. Else
// returns distance of x from root
int findDistance(Node *root, int x)
{
    // Base case
    if (root == NULL)
      return -1;
 
    // Initialize distance
    int dist = -1;
 
    // Check if x is present at root or in left
    // subtree or right subtree.
    if ((root->data == x) ||
        (dist = findDistance(root->left, x)) >= 0 ||
        (dist = findDistance(root->right, x)) >= 0)
        return dist + 1;
 
    return dist;
}
 
// Driver Program to test above functions
int main()
{
    Node *root = newNode(5);
    root->left = newNode(10);
    root->right = newNode(15);
    root->left->left = newNode(20);
    root->left->right = newNode(25);
    root->left->right->right = newNode(45);
    root->right->left = newNode(30);
    root->right->right = newNode(35);
 
    cout << findDistance(root, 45);
    return 0;
}

Java

// Java program to find distance of a given
// node from root.
import java.util.*;
class GfG {
 
// A Binary Tree Node
static class Node
{
    int data;
    Node left, right;
}
 
// A utility function to create a new Binary
// Tree Node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// Returns -1 if x doesn't exist in tree. Else
// returns distance of x from root
static int findDistance(Node root, int x)
{
    // Base case
    if (root == null)
    return -1;
 
    // Initialize distance
    int dist = -1;
 
    // Check if x is present at root or in left
    // subtree or right subtree.
    if ((root.data == x) ||
        (dist = findDistance(root.left, x)) >= 0 ||
        (dist = findDistance(root.right, x)) >= 0)
        return dist + 1;
 
    return dist;
}
 
// Driver Program to test above functions
public static void main(String[] args)
{
    Node root = newNode(5);
    root.left = newNode(10);
    root.right = newNode(15);
    root.left.left = newNode(20);
    root.left.right = newNode(25);
    root.left.right.right = newNode(45);
    root.right.left = newNode(30);
    root.right.right = newNode(35);
 
    System.out.println(findDistance(root, 45));
}
}

Python3

# Python3 program to find distance of
# a given node from root.
 
# A class to create a new Binary
# Tree Node
class newNode:
    def __init__(self, item):
        self.data = item
        self.left = self.right = None
 
# Returns -1 if x doesn't exist in tree.
# Else returns distance of x from root
def findDistance(root, x):
     
    # Base case
    if (root == None):
        return -1
 
    # Initialize distance
    dist = -1
 
    # Check if x is present at root or
    # in left subtree or right subtree.
    if (root.data == x):
        return dist + 1
    else:
        dist = findDistance(root.left, x)
        if dist >= 0:
            return dist + 1
        else:
            dist = findDistance(root.right, x)
            if dist >= 0:
                return dist + 1
 
    return dist
 
# Driver Code
if __name__ == '__main__':
 
    root = newNode(5)
    root.left = newNode(10)
    root.right = newNode(15)
    root.left.left = newNode(20)
    root.left.right = newNode(25)
    root.left.right.right = newNode(45)
    root.right.left = newNode(30)
    root.right.right = newNode(35)
 
    print(findDistance(root, 45))
 
# This code is contributed by PranchalK

C#

// C# program to find distance of a given
// node from root.
using System;
 
class GfG
{
 
    // A Binary Tree Node
    class Node
    {
        public int data;
        public Node left, right;
    }
 
    // A utility function to create 
    // a new Binary Tree Node
    static Node newNode(int item)
    {
        Node temp = new Node();
        temp.data = item;
        temp.left = null;
        temp.right = null;
        return temp;
    }
 
    // Returns -1 if x doesn't exist in tree. Else
    // returns distance of x from root
    static int findDistance(Node root, int x)
    {
        // Base case
        if (root == null)
        return -1;
 
        // Initialize distance
        int dist = -1;
 
        // Check if x is present at root or in left
        // subtree or right subtree.
        if ((root.data == x) ||
            (dist = findDistance(root.left, x)) >= 0 ||
            (dist = findDistance(root.right, x)) >= 0)
            return dist + 1;
 
        return dist;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        Node root = newNode(5);
        root.left = newNode(10);
        root.right = newNode(15);
        root.left.left = newNode(20);
        root.left.right = newNode(25);
        root.left.right.right = newNode(45);
        root.right.left = newNode(30);
        root.right.right = newNode(35);
 
        Console.WriteLine(findDistance(root, 45));
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to find distance
// of a given node from root.
 
// A Binary Tree Node
class Node
{
     
    // A utility function to create a
    // new Binary Tree Node
    constructor(data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
 
// Returns -1 if x doesn't exist in tree. Else
// returns distance of x from root
function findDistance(root, x)
{
     
    // Base case
    if (root == null)
        return -1;
  
    // Initialize distance
    let dist = -1;
  
    // Check if x is present at root or in left
    // subtree or right subtree.
    if ((root.data == x) ||
        (dist = findDistance(root.left, x)) >= 0 ||
        (dist = findDistance(root.right, x)) >= 0)
        return dist + 1;
  
    return dist;
}
 
// Driver code
let root = new Node(5);
root.left = new Node(10);
root.right = new Node(15);
root.left.left = new Node(20);
root.left.right = new Node(25);
root.left.right.right = new Node(45);
root.right.left = new Node(30);
root.right.right = new Node(35);
 
document.write(findDistance(root, 45));
 
// This code is contributed by rag2127
 
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *