Dados dos enteros N y X , donde N es el número de Nodes en un árbol binario casi completo . La tarea es encontrar:
- El número de Nodes que están a una distancia X de la raíz.
- El número de Nodes que están a una distancia X de cualquier hoja en su subárbol.
Nota: Un árbol binario completo es un árbol binario en el que todos los niveles, excepto posiblemente el último, están completamente llenos y todos los Nodes están lo más a la izquierda posible.
Ejemplos:
Input: N = 6, X = 0
Output:
1
3
Complete Binary Tree of 6 nodes is
1
/ \
2 3
/ \ /
4 5 6
Nodes that are at 0 distance from root = 1 (root itself).
Nodes that are at 0 distance from any of the leaf = 3 (all the leaves of the tree)
Input: N = 13, X = 1
Output:
2
4
Complete Binary Tree of 13 nodes.
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \
8 9 10 11 12 13
Nodes that are at 0 distance from root = 2 (node no. 2 and 3)
Nodes that are at 0 distance from any of the leaf = 4 (node no. 4, 5, 6 and 3)
Acercarse:
- Encontrar el número de Nodes que están a una distancia x de la raíz es simple. Simplemente imprimimos el número de Nodes a la x-ésima altura. Sabemos que en un árbol binario completo todos los niveles están completos, excepto posiblemente el último y todos los Nodes están lo más a la izquierda posible. Entonces, la altura h de un árbol binario completo se calcula como piso (log2 (n)) donde n es el número total de Nodes. Además, el número de Nodes en la i-ésima altura será 2 i y el número de Nodes que están en el último nivel (es decir, en la altura h) = 2 h – (max_total_nodes – n) , donde 2 h son Nodes máximos en la altura h .
- Encontrar el número de Nodes que están a una distancia x de cualquier hoja en su subárbol es un poco complicado. Se trata de observar el hecho de que si tenemos l Nodes hoja entonces, los Nodes ceil(l/2) están a 1 unidad de distancia de las hojas, los Nodes ceil(l/4) están a 2 unidades de distancia de las hojas…. hasta ceil(l/2 i ) los Nodes están a i unidades de distancia de las hojas. Primero encontraremos el conteo de Nodes hoja y aplicaremos el método anterior para encontrar Nodes que estén a una distancia x de la hoja.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count
// of the required nodes
void countNodes(int N, int X)
{
// Height of the complete binary
// tree with n nodes
int height = floor(log2(N));
// If X > height then no node
// can be present at that level
if (X > height) {
cout << "0\n0";
return;
}
// Corner case
if (N == 1) {
cout << "1\n1";
return;
}
// Maximum total nodes that are possible
// in complete binary tree with height h
int max_total_nodes = (1 << (height + 1)) - 1;
// Nodes at the last level
int nodes_last_level
= (1 << height) - (max_total_nodes - N);
// To store the count of nodes
// x dist away from root
int from_root;
// To store the count of nodes
// x dist away from leaf
int from_leaf;
// If X = h then print nodes at last level
// else nodes at Xth level
if (X == height)
from_root = nodes_last_level;
// 2^X
else
from_root = 1 << X;
// Number of left leaf nodes at (h-1)th level
// observe that if nodes are not present at last level
// then there are a/2 leaf nodes at (h-1)th level
int left_leaf_nodes
= ((1 << height) - nodes_last_level) / 2;
// If X = h then print leaf nodes at the last h level
// + leaf nodes at (h-1)th level
if (X == 0) {
from_leaf = nodes_last_level + left_leaf_nodes;
}
else {
// First calculate nodes for leaves present at
// height h
int i = X;
while (nodes_last_level > 1 && i > 0) {
nodes_last_level
= ceil((float)nodes_last_level / (float)2);
i--;
}
from_leaf = nodes_last_level;
// Then calculate nodes for leaves present at height
// h-1
i = X;
while (left_leaf_nodes > 1 && i > 0) {
left_leaf_nodes
= ceil((float)left_leaf_nodes / (float)2);
i--;
}
// Add both the results
from_leaf += left_leaf_nodes;
}
cout << from_root << endl << from_leaf;
}
// Driver code
int main()
{
int N = 38, X = 3;
countNodes(N, X);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to find the count
// of the required nodes
static void countNodes(int N, int X)
{
// Height of the complete binary
// tree with n nodes
int height
= (int)Math.floor(Math.log(N) / Math.log(2));
// If X > height then no node
// can be present at that level
if (X > height) {
System.out.println("0\n0");
return;
}
// Corner case
if (N == 1) {
System.out.println("1\n1");
return;
}
// Maximum total nodes that are possible
// in complete binary tree with height h
int max_total_nodes = (1 << (height + 1)) - 1;
// Nodes at the last level
int nodes_last_level
= (1 << height) - (max_total_nodes - N);
// To store the count of nodes
// x dist away from root
int from_root;
// To store the count of nodes
// x dist away from leaf
int from_leaf;
// If X = h then print nodes at last level
// else nodes at Xth level
if (X == height)
from_root = nodes_last_level;
// 2^X
else
from_root = 1 << X;
// Number of left leaf nodes at (h-1)th level
// observe that if nodes are not present at last
// level then there are a/2 leaf nodes at (h-1)th
// level
int left_leaf_nodes
= ((1 << height) - nodes_last_level) / 2;
// If X = h then print leaf nodes at the last h
// level
// + leaf nodes at (h-1)th level
if (X == 0) {
from_leaf = nodes_last_level + left_leaf_nodes;
}
else {
// First calculate nodes for leaves present at
// height h
int i = X;
while (nodes_last_level > 1 && i > 0) {
nodes_last_level = (int)Math.ceil(
(float)nodes_last_level / (float)2);
i--;
}
from_leaf = nodes_last_level;
// Then calculate nodes for leaves present at
// height h-1
i = X;
while (left_leaf_nodes > 1 && i > 0) {
left_leaf_nodes = (int)Math.ceil(
(float)left_leaf_nodes / (float)2);
i--;
}
// Add both the results
from_leaf += left_leaf_nodes;
}
System.out.println(from_root + "\n" + from_leaf);
}
// Driver Code
public static void main(String[] args)
{
int N = 38, X = 3;
countNodes(N, X);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach
from math import log2, ceil, floor
# Function to find the count
# of the required nodes
def countNodes(N, X):
# Height of the complete binary
# tree with n nodes
height = floor(log2(N))
# If X > height then no node
# can be present at that level
if (X > height):
print("0\n0")
return
# Corner case
if (N == 1):
print("1\n1")
return
# Maximum total nodes that are possible
# in complete binary tree with height h
max_total_nodes = (1 << (height + 1)) - 1
# Nodes at the last level
nodes_last_level = (1 << height) - (max_total_nodes - N)
# To store the count of nodes
# x dist away from root
from_root = 0
# To store the count of nodes
# x dist away from leaf
from_leaf = 0
# If X = h then print nodes at last level
# else nodes at Xth level
if (X == height):
from_root = nodes_last_level
# 2^X
else:
from_root = 1 << X
# Number of left leaf nodes at (h-1)th level
# observe that if nodes are not present at last level
# then there are a/2 leaf nodes at (h-1)th level
left_leaf_nodes = ((1 << height) - nodes_last_level) // 2
# If X = h then print leaf nodes at the last h level
# + leaf nodes at (h-1)th level
if (X == 0):
from_leaf = nodes_last_level + left_leaf_nodes
else:
# First calculate nodes for leaves present at
# height h
i = X
while (nodes_last_level > 1 and i > 0):
nodes_last_level = ceil(nodes_last_level / 2)
i-=1
from_leaf = nodes_last_level
# Then calculate nodes for leaves present at height
# h-1
i = X
while (left_leaf_nodes > 1 and i > 0):
left_leaf_nodes = ceil(left_leaf_nodes / 2)
i -= 1
# Add both the results
from_leaf += left_leaf_nodes
print(from_root)
print(from_leaf)
# Driver code
if __name__ == '__main__':
N, X = 38, 3
countNodes(N, X)
# This code is contributed by mohit kumar 29.
C#
// C# implementation of the approach
using System;
class GFG{
// Function to find the count
// of the required nodes
static void countNodes(int N, int X)
{
// Height of the complete binary
// tree with n nodes
int height = (int)Math.Floor(Math.Log(N) /
Math.Log(2));
// If X > height then no node
// can be present at that level
if (X > height)
{
Console.Write("0\n0");
return;
}
// Corner case
if (N == 1)
{
Console.Write("1\n1");
return;
}
// Maximum total nodes that are possible
// in complete binary tree with height h
int max_total_nodes = (1 << (height + 1)) - 1;
// Nodes at the last level
int nodes_last_level = (1 << height) -
(max_total_nodes - N);
// To store the count of nodes
// x dist away from root
int from_root;
// To store the count of nodes
// x dist away from leaf
int from_leaf;
// If X = h then print nodes at last level
// else nodes at Xth level
if (X == height)
from_root = nodes_last_level;
// 2^X
else
from_root = 1 << X;
// Number of left leaf nodes at (h-1)th level
// observe that if nodes are not present at last
// level then there are a/2 leaf nodes at (h-1)th
// level
int left_leaf_nodes = ((1 << height) -
nodes_last_level) / 2;
// If X = h then print leaf nodes at the last h
// level
// + leaf nodes at (h-1)th level
if (X == 0)
{
from_leaf = nodes_last_level +
left_leaf_nodes;
}
else
{
// First calculate nodes for leaves present
// at height h
int i = X;
while (nodes_last_level > 1 && i > 0)
{
nodes_last_level = (int)Math.Ceiling(
(float)nodes_last_level / (float)2);
i--;
}
from_leaf = nodes_last_level;
// Then calculate nodes for leaves present at
// height h-1
i = X;
while (left_leaf_nodes > 1 && i > 0)
{
left_leaf_nodes = (int)Math.Ceiling(
(float)left_leaf_nodes / (float)2);
i--;
}
// Add both the results
from_leaf += left_leaf_nodes;
}
Console.Write(from_root + "\n" + from_leaf);
}
// Driver Code
public static void Main()
{
int N = 38, X = 3;
countNodes(N, X);
}
}
// This code is contributed by subham348
Javascript
<script>
// Javascript implementation of the approach
// Function to find the count
// of the required nodes
function countNodes(N, X)
{
// Height of the complete binary
// tree with n nodes
let height = Math.floor(Math.log(N) /
Math.log(2));
// If X > height then no node
// can be present at that level
if (X > height)
{
document.write("0<br>0");
return;
}
// Corner case
if (N == 1)
{
document.write("1<br>1");
return;
}
// Maximum total nodes that are possible
// in complete binary tree with height h
let max_total_nodes = (1 << (height + 1)) - 1;
// Nodes at the last level
let nodes_last_level = (1 << height) -
(max_total_nodes - N);
// To store the count of nodes
// x dist away from root
let from_root;
// To store the count of nodes
// x dist away from leaf
let from_leaf;
// If X = h then print nodes at last level
// else nodes at Xth level
if (X == height)
from_root = nodes_last_level;
// 2^X
else
from_root = 1 << X;
// Number of left leaf nodes at (h-1)th level
// observe that if nodes are not present at last
// level then there are a/2 leaf nodes at (h-1)th
// level
let left_leaf_nodes = Math.floor(
((1 << height) - nodes_last_level) / 2);
// If X = h then print leaf nodes at the last h
// level
// + leaf nodes at (h-1)th level
if (X == 0)
{
from_leaf = nodes_last_level +
left_leaf_nodes;
}
else
{
// First calculate nodes for leaves
// present at height h
let i = X;
while (nodes_last_level > 1 && i > 0)
{
nodes_last_level = Math.floor(Math.ceil(
nodes_last_level / 2));
i--;
}
from_leaf = nodes_last_level;
// Then calculate nodes for leaves present at
// height h-1
i = X;
while (left_leaf_nodes > 1 && i > 0)
{
left_leaf_nodes = Math.floor(Math.ceil(
left_leaf_nodes / 2));
i--;
}
// Add both the results
from_leaf += left_leaf_nodes;
}
document.write(from_root + "<br>" + from_leaf);
}
// Driver Code
let N = 38, X = 3;
countNodes(N, X);
// This code is contributed by unknown2108
</script>
Producción:
8 3
Complejidad del tiempo: O(log (N) )
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por tyagikartik4282 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA