Dado un árbol binario y un entero X, la tarea es encontrar todas las ocurrencias de X en el árbol dado e imprimir su nivel y su posición de izquierda a derecha en ese nivel. Si no se encuentra X , imprima -1.
Ejemplos:
Entrada: X=35
10
/ \
20 30
/ \ / \
40 60 35 50
Salida: [( 3, 3)]
Explicación: el entero X=35 está presente en el nivel 3 y su posición es 3 desde la izquierda.Entrada: X= 2
1
/ \
2 3
/ \ / \
4 6 8 2
Salida: [(2, 1), (3, 4)]
Explicación: el entero X=2 está presente en el nivel 2 y su posición es 1 desde izquierda también está presente en el nivel 3 y la posición desde la izquierda es 4.
Enfoque : Este problema se puede resolver mediante el cruce de orden de niveles del árbol binario mediante la cola .
- Realice un recorrido de orden de niveles de un árbol binario determinado mediante la cola.
- Realice un seguimiento del recuento de niveles y el recuento de Nodes de izquierda a derecha durante el recorrido
- Siempre que se encuentre X durante el recorrido, imprima o almacene el recuento de niveles y la posición de la aparición actual de X.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print level and
// position of Node X in binary tree
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
// Function to find and print
// level and position of node X
void printLevelandPosition(Node* root, int X)
{
// Base Case
if (root == NULL)
return;
// Create an empty queue
queue<Node*> q;
// Enqueue Root and initialize height
q.push(root);
// Create and initialize current
// level and position by 1
int currLevel = 1, position = 1;
while (q.empty() == false) {
int size = q.size();
while (size--) {
Node* node = q.front();
// print if node data equal to X
if (node->data == X)
cout << "(" << currLevel
<< " " << position
<< "), ";
q.pop();
// increment the position
position++;
// Enqueue left child
if (node->left != NULL)
q.push(node->left);
// Enqueue right child
if (node->right != NULL)
q.push(node->right);
}
// increment the level
currLevel++;
position = 1;
}
}
// Utility function to create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(2);
int X = 2;
printLevelandPosition(root, X);
return 0;
}
Java
// JAVA program to print level and
// position of Node X in binary tree
import java.util.*;
// A Binary Tree Node
class Node {
int data;
Node left;
Node right;
}
class GFG
{
// Function to find and print
// level and position of node X
public static void printLevelandPosition(Node root,
int X)
{
// Base Case
if (root == null)
return;
// Create an empty queue
Queue<Node> q = new LinkedList<>();
// Enqueue Root and initialize height
q.add(root);
// Create and initialize current
// level and position by 1
int currLevel = 1, position = 1;
while (q.size() != 0) {
int size = q.size();
while ((size--) != 0) {
Node node = q.peek();
// print if node data equal to X
if (node.data == X)
System.out.print("(" + currLevel + " "
+ position + "), ");
q.remove();
// increment the position
position++;
// Enqueue left child
if (node.left != null)
q.add(node.left);
// Enqueue right child
if (node.right != null)
q.add(node.right);
}
// increment the level
currLevel++;
position = 1;
}
}
// Utility function to create a new tree node
public static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver program to test above functions
public static void main(String[] args)
{
// Let us create binary tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(2);
int X = 2;
printLevelandPosition(root, X);
}
}
// This code is contributed by Taranpreet
Python3
# Python code for the above approach
class Node:
def __init__(self,d):
self.data = d
self.left = None
self.right = None
# Function to find and print
# level and position of node X
def printLevelandPosition(root, X):
# Base Case
if (root == None):
return
# Create an empty queue
q = []
# Enqueue Root and initialize height
q.append(root)
# Create and initialize current
# level and position by 1
currLevel,position = 1,1
while (len(q) != 0):
size = len(q)
while (size != 0):
node = q[0]
q = q[1:]
# print if node data equal to X
if (node.data == X):
print (f"({currLevel} {position}),",end =" ")
# increment the position
position += 1
# Enqueue left child
if (node.left != None):
q.append(node.left)
# Enqueue right child
if (node.right != None):
q.append(node.right)
size -= 1
# increment the level
currLevel += 1
position = 1
# Driver program to test above functions
# Let us create binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(2)
X = 2
printLevelandPosition(root, X)
# This code is contributed by shinjanpatra
C#
// C# program to print level and
// position of Node X in binary tree
using System;
using System.Collections.Generic;
// A Binary Tree Node
public class Node {
public int data;
public Node left;
public Node right;
}
public class GFG {
// Function to find and print
// level and position of node X
public static void printLevelandPosition(Node root, int X) {
// Base Case
if (root == null)
return;
// Create an empty queue
Queue<Node> q = new Queue<Node>();
// Enqueue Root and initialize height
q.Enqueue(root);
// Create and initialize current
// level and position by 1
int currLevel = 1, position = 1;
while (q.Count != 0) {
int size = q.Count;
while ((size--) != 0) {
Node node = q.Peek();
// print if node data equal to X
if (node.data == X)
Console.Write("(" + currLevel + " " + position + "), ");
q.Dequeue();
// increment the position
position++;
// Enqueue left child
if (node.left != null)
q.Enqueue(node.left);
// Enqueue right child
if (node.right != null)
q.Enqueue(node.right);
}
// increment the level
currLevel++;
position = 1;
}
}
// Utility function to create a new tree node
public static Node newNode(int data) {
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver program to test above functions
public static void Main(String[] args) {
// Let us create binary tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(2);
int X = 2;
printLevelandPosition(root, X);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
class Node {
constructor(d) {
this.data = d;
this.left = null;
this.right = null;
}
}
// Function to find and print
// level and position of node X
function printLevelandPosition(root, X)
{
// Base Case
if (root == null)
return;
// Create an empty queue
let q = [];
// Enqueue Root and initialize height
q.push(root);
// Create and initialize current
// level and position by 1
let currLevel = 1, position = 1;
while (q.length != 0) {
let size = q.length;
while (size-- != 0) {
let node = q.shift();
// print if node data equal to X
if (node.data == X)
document.write("(" + currLevel
+ " " + position
+ "), ");
// increment the position
position++;
// Enqueue left child
if (node.left != null)
q.push(node.left);
// Enqueue right child
if (node.right != null)
q.push(node.right);
}
// increment the level
currLevel++;
position = 1;
}
}
// Driver program to test above functions
// Let us create binary tree
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(2);
let X = 2;
printLevelandPosition(root, X);
// This code is contributed by Potta Lokesh
</script>
Producción
(2 1), (3 2),
Complejidad temporal: O(n)
Espacio auxiliar: O(n)