Dado un árbol binario que consta de N Nodes y un número entero K , la tarea es encontrar la profundidad y la altura del Node con valor K en el árbol binario .
La profundidad de un Node es el número de aristas presentes en la ruta desde el Node raíz de un árbol hasta ese Node.
La altura de un Node es el número de aristas presentes en el camino más largo que conecta ese Node con un Node hoja.
Ejemplos:
Entrada: K = 25,
5
/ \
10 15
/ \ / \
20 25 30 35
\
45
Salida:
Profundidad del Node 25 = 2
Altura del Node 25 = 1
Explicación:
El número de aristas en la ruta desde el Node raíz hasta el Node 25 es 2. Por lo tanto, la profundidad del Node 25 es 2.
El número de aristas en el camino más largo que conecta el Node 25 con cualquier Node hoja es 1. Por lo tanto, la altura del Node 25 es 1.Entrada: K = 10,
5
/ \
10 15
/ \ / \
20 25 30 35
\
45
Salida:
Profundidad del Node 10 = 1
Altura del Node 10 = 2
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
Profundidad de un Node K (de un árbol binario ) = Número de aristas en el camino que conecta la raíz con el Node K = Número de ancestros de K (excluyendo K mismo).
Siga los pasos a continuación para encontrar la profundidad del Node dado:
- Si el árbol está vacío, imprima -1.
- De lo contrario, realice los siguientes pasos:
- Inicialice una variable, diga dist como -1 .
- Compruebe si el Node K es igual al Node dado.
- De lo contrario, verifique si está presente en cualquiera de los subárboles, verificando recursivamente los subárboles izquierdo y derecho respectivamente.
- Si es cierto, imprime el valor de dist + 1 .
- De lo contrario, imprima dist .
Altura de un Node K (de un árbol binario ) = Número de aristas en el camino más largo que conecta K con cualquier Node hoja.
Siga los pasos a continuación para encontrar la altura del Node dado:
- Si el árbol está vacío, imprima -1.
- De lo contrario, realice los siguientes pasos:
- Calcule la altura del subárbol izquierdo recursivamente.
- Calcule la altura del subárbol derecho recursivamente.
- Actualice la altura del Node actual sumando 1 al máximo de las dos alturas obtenidas en el paso anterior. Almacene la altura en una variable, digamos ans .
- Si el Node actual es igual al Node K dado, imprima el valor de ans como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of a Binary Tree Node struct Node { int data; Node *left, *right; }; // 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 the depth of // a given node in a Binary Tree int findDepth(Node* root, int x) { // Base case if (root == NULL) return -1; // Initialize distance as -1 int dist = -1; // Check if x is current node= if ((root->data == x) // Otherwise, check if x is // present in the left subtree || (dist = findDepth(root->left, x)) >= 0 // Otherwise, check if x is // present in the right subtree || (dist = findDepth(root->right, x)) >= 0) // Return depth of the node return dist + 1; return dist; } // Helper function to find the height // of a given node in the binary tree int findHeightUtil(Node* root, int x, int& height) { // Base Case if (root == NULL) { return -1; } // Store the maximum height of // the left and right subtree int leftHeight = findHeightUtil( root->left, x, height); int rightHeight = findHeightUtil( root->right, x, height); // Update height of the current node int ans = max(leftHeight, rightHeight) + 1; // If current node is the required node if (root->data == x) height = ans; return ans; } // Function to find the height of // a given node in a Binary Tree int findHeight(Node* root, int x) { // Store the height of // the given node int h = -1; // Stores height of the Tree int maxHeight = findHeightUtil(root, x, h); // Return the height return h; } // Driver Code int main() { // Binary Tree Formation 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); int k = 25; // Function call to find the // depth of a given node cout << "Depth: " << findDepth(root, k) << "\n"; // Function call to find the // height of a given node cout << "Height: " << findHeight(root, k); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { static int height = -1; // Structure of a Binary Tree Node static class Node { int data; Node left; Node right; }; // 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 the depth of // a given node in a Binary Tree static int findDepth(Node root, int x) { // Base case if (root == null) return -1; // Initialize distance as -1 int dist = -1; // Check if x is current node= if ((root.data == x)|| // Otherwise, check if x is // present in the left subtree (dist = findDepth(root.left, x)) >= 0 || // Otherwise, check if x is // present in the right subtree (dist = findDepth(root.right, x)) >= 0) // Return depth of the node return dist + 1; return dist; } // Helper function to find the height // of a given node in the binary tree static int findHeightUtil(Node root, int x) { // Base Case if (root == null) { return -1; } // Store the maximum height of // the left and right subtree int leftHeight = findHeightUtil(root.left, x); int rightHeight = findHeightUtil(root.right, x); // Update height of the current node int ans = Math.max(leftHeight, rightHeight) + 1; // If current node is the required node if (root.data == x) height = ans; return ans; } // Function to find the height of // a given node in a Binary Tree static int findHeight(Node root, int x) { // Stores height of the Tree findHeightUtil(root, x); // Return the height return height; } // Driver Code public static void main(String []args) { // Binary Tree Formation 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); int k = 25; // Function call to find the // depth of a given node System.out.println("Depth: " + findDepth(root, k)); // Function call to find the // height of a given node System.out.println("Height: " + findHeight(root, k)); } } // This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 program for the above approach # Structure of a Binary Tree Node class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Function to find the depth of # a given node in a Binary Tree def findDepth(root, x): # Base case if (root == None): return -1 # Initialize distance as -1 dist = -1 # Check if x is current node= if (root.data == x): return dist + 1 dist = findDepth(root.left, x) if dist >= 0: return dist + 1 dist = findDepth(root.right, x) if dist >= 0: return dist + 1 return dist # Helper function to find the height # of a given node in the binary tree def findHeightUtil(root, x): global height # Base Case if (root == None): return -1 # Store the maximum height of # the left and right subtree leftHeight = findHeightUtil(root.left, x) rightHeight = findHeightUtil(root.right, x) # Update height of the current node ans = max(leftHeight, rightHeight) + 1 # If current node is the required node if (root.data == x): height = ans return ans # Function to find the height of # a given node in a Binary Tree def findHeight(root, x): global height # Stores height of the Tree maxHeight = findHeightUtil(root, x) # Return the height return height # Driver Code if __name__ == '__main__': # Binary Tree Formation height = -1 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) k = 25 # Function call to find the # depth of a given node print("Depth: ",findDepth(root, k)) # Function call to find the # height of a given node print("Height: ",findHeight(root, k)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ static int height = -1; // Structure of a Binary Tree Node class Node { public int data; public Node left; public Node right; }; // 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 the depth of // a given node in a Binary Tree static int findDepth(Node root, int x) { // Base case if (root == null) return -1; // Initialize distance as -1 int dist = -1; // Check if x is current node= if ((root.data == x)|| // Otherwise, check if x is // present in the left subtree (dist = findDepth(root.left, x)) >= 0 || // Otherwise, check if x is // present in the right subtree (dist = findDepth(root.right, x)) >= 0) // Return depth of the node return dist + 1; return dist; } // Helper function to find the height // of a given node in the binary tree static int findHeightUtil(Node root, int x) { // Base Case if (root == null) { return -1; } // Store the maximum height of // the left and right subtree int leftHeight = findHeightUtil(root.left, x); int rightHeight = findHeightUtil(root.right, x); // Update height of the current node int ans = Math.Max(leftHeight, rightHeight) + 1; // If current node is the required node if (root.data == x) height = ans; return ans; } // Function to find the height of // a given node in a Binary Tree static int findHeight(Node root, int x) { // Stores height of the Tree findHeightUtil(root, x); // Return the height return height; } // Driver Code public static void Main() { // Binary Tree Formation 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); int k = 25; // Function call to find the // depth of a given node Console.WriteLine("Depth: " + findDepth(root, k)); // Function call to find the // height of a given node Console.WriteLine("Height: " + findHeight(root, k)); } } // This code is contributed by ipg2016107
Javascript
<script> // JavaScript program for the above approach var height = -1; // Structure of a Binary Tree Node class Node { constructor() { this.data = 0; this.left = null; this.right = null; } }; // Utility function to create // a new Binary Tree Node function newNode(item) { var temp = new Node(); temp.data = item; temp.left = temp.right = null; return temp; } // Function to find the depth of // a given node in a Binary Tree function findDepth(root, x) { // Base case if (root == null) return -1; // Initialize distance as -1 var dist = -1; // Check if x is current node= if ((root.data == x)|| // Otherwise, check if x is // present in the left subtree (dist = findDepth(root.left, x)) >= 0 || // Otherwise, check if x is // present in the right subtree (dist = findDepth(root.right, x)) >= 0) // Return depth of the node return dist + 1; return dist; } // Helper function to find the height // of a given node in the binary tree function findHeightUtil(root, x) { // Base Case if (root == null) { return -1; } // Store the maximum height of // the left and right subtree var leftHeight = findHeightUtil(root.left, x); var rightHeight = findHeightUtil(root.right, x); // Update height of the current node var ans = Math.max(leftHeight, rightHeight) + 1; // If current node is the required node if (root.data == x) height = ans; return ans; } // Function to find the height of // a given node in a Binary Tree function findHeight(root, x) { // Stores height of the Tree findHeightUtil(root, x); // Return the height return height; } // Driver Code // Binary Tree Formation var 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); var k = 25; // Function call to find the // depth of a given node document.write("Depth: " + findDepth(root, k)+"<br>"); // Function call to find the // height of a given node document.write("Height: " + findHeight(root, k)); </script>
Depth: 2 Height: 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)