Dada la raíz de un árbol binario y una clave x en él, encuentre la distancia de la clave dada desde el Node raíz. Distancia significa el número de aristas entre dos Nodes.
Ejemplos :
Input : x = 45, 5 is Root of below tree 5 / \ 10 15 / \ / \ 20 25 30 35 \ 45 Output : Distance = 3 There are three edges on path from root to 45. For more understanding of question, in above tree distance of 35 is two and distance of 10 is 1.
Problema relacionado : programa recursivo para encontrar la distancia del Node desde la raíz .
Enfoque iterativo :
- Utilice el recorrido por orden de niveles para recorrer el árbol de forma iterativa mediante una cola.
- Mantenga una variable levelCount para mantener la pista del nivel actual.
- Para hacer esto, cada vez que pase al siguiente nivel, mientras empuja un Node NULL a la cola, también incremente el valor de la variable levelCount para que almacene el número de nivel actual.
- Mientras recorre el árbol, verifique si algún Node en el nivel actual coincide con la clave dada.
- En caso afirmativo, devuelva levelCount.
A continuación se muestra la implementación del enfoque anterior:
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; } /* Function to find distance of a node from root * root : root of the Tree * key : data whose distance to be calculated */ int findDistance(Node* root, int key) { // base case if (root == NULL) { return -1; } // If the key is present at root, // distance is zero if (root->data == key) return 0; // Iterating through tree using BFS queue<Node*> q; // pushing root to the queue q.push(root); // pushing marker to the queue q.push(NULL); // Variable to store count of level int levelCount = 0; while (!q.empty()) { Node* temp = q.front(); q.pop(); // if node is marker, push marker to queue // else, push left and right (if exists) if (temp == NULL && !q.empty()) { q.push(NULL); // Increment levelCount, while moving // to new level levelCount++; } else if (temp != NULL) { // If node at current level is Key, // return levelCount if (temp->data == key) return levelCount; if (temp->left) q.push(temp->left); if (temp->right) q.push(temp->right); } } // If key is not found return -1; } // Driver Code 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 = temp.right = null; return temp; } /* Function to find distance of a node from root * root : root of the Tree * key : data whose distance to be calculated */ static int findDistance(Node root, int key) { // base case if (root == null) { return -1; } // If the key is present at root, // distance is zero if (root.data == key) return 0; // Iterating through tree using BFS Queue<Node> q = new LinkedList<Node>(); // adding root to the queue q.add(root); // adding marker to the queue q.add(null); // Variable to store count of level int levelCount = 0; while (!q.isEmpty()) { Node temp = q.peek(); q.remove(); // if node is marker, push marker to queue // else, push left and right (if exists) if (temp == null && !q.isEmpty()) { q.add(null); // Increment levelCount, while moving // to new level levelCount++; } else if (temp != null) { // If node at current level is Key, // return levelCount if (temp.data == key) return levelCount; if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } } // If key is not found return -1; } // 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); System.out.println(findDistance(root, 45)); } } // This code is contributed by Rajput-Ji
Python3
# Python program to find distance of a given # node from root. from collections import deque # A tree binary node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to find distance of a node from root # root : root of the Tree # key : data whose distance to be calculated def findDistance(root: Node, key: int) -> int: # base case if root is None: return -1 # If the key is present at root, # distance is zero if root.data == key: return 0 # Iterating through tree using BFS q = deque() # pushing root to the queue q.append(root) # pushing marker to the queue q.append(None) # Variable to store count of level levelCount = 0 while q: temp = q[0] q.popleft() # if node is marker, push marker to queue # else, push left and right (if exists) if temp is None and q: q.append(None) # Increment levelCount, while moving # to new level levelCount += 1 elif temp: # If node at current level is Key, # return levelCount if temp.data == key: return levelCount if temp.left: q.append(temp.left) if temp.right: q.append(temp.right) # If key is not found return -1 # Driver Code if __name__ == "__main__": root = Node(5) root.left = Node(10) root.right = Node(15) root.left.left = Node(20) root.left.right = Node(25) root.left.right.right = Node(45) root.right.left = Node(30) root.right.right = Node(35) print(findDistance(root, 45)) # This code is contributed by # sanjeev2552
C#
// C# program to find distance of a given // node from root. using System; using System.Collections.Generic; 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 = temp.right = null; return temp; } /* Function to find distance of a node from root * root : root of the Tree * key : data whose distance to be calculated*/ static int findDistance(Node root, int key) { // base case if (root == null) { return -1; } // If the key is present at root, // distance is zero if (root.data == key) return 0; // Iterating through tree using BFS Queue<Node> q = new Queue<Node>(); // adding root to the queue q.Enqueue(root); // adding marker to the queue q.Enqueue(null); // Variable to store count of level int levelCount = 0; while (q.Count!=0) { Node temp = q.Peek(); q.Dequeue(); // if node is marker, push marker to queue // else, push left and right (if exists) if (temp == null && q.Count!=0) { q.Enqueue(null); // Increment levelCount, while moving // to new level levelCount++; } else if (temp != null) { // If node at current level is Key, // return levelCount if (temp.data == key) return levelCount; if (temp.left != null) q.Enqueue(temp.left); if (temp.right != null) q.Enqueue(temp.right); } } // If key is not found return -1; } // 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 Princi Singh
Javascript
<script> // Javascript program to find distance // of a given node from root. // A Binary Tree Node class Node { constructor(item) { this.left = null; this.right = null; this.data = item; } } // A utility function to create a new Binary // Tree Node function newNode(item) { let temp = new Node(item); return temp; } /* Function to find distance of a node from root * root : root of the Tree * key : data whose distance to be calculated */ function findDistance(root, key) { // Base case if (root == null) { return -1; } // If the key is present at root, // distance is zero if (root.data == key) return 0; // Iterating through tree using BFS let q = []; // Adding root to the queue q.push(root); // Adding marker to the queue q.push(null); // Variable to store count of level let levelCount = 0; while (q.length > 0) { let temp = q[0]; q.shift(); // If node is marker, push marker to queue // else, push left and right (if exists) if (temp == null && q.length > 0) { q.push(null); // Increment levelCount, while moving // to new level levelCount++; } else if (temp != null) { // If node at current level is Key, // return levelCount if (temp.data == key) return levelCount; if (temp.left != null) q.push(temp.left); if (temp.right != null) q.push(temp.right); } } // If key is not found return -1; } // Driver code let 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); document.write(findDistance(root, 45)); // This code is contributed by suresh07 </script>
Producción:
3