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>
Producción:
Depth: 2 Height: 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)