Dado un árbol binario y un Node en el árbol binario, encuentre el sucesor de Levelorder del Node dado. Es decir, el Node que aparece después del Node dado en el recorrido de orden de niveles del árbol.
Nota : la tarea no es solo imprimir los datos del Node, debe devolver el Node completo del árbol.
Ejemplos :
Consider the following binary tree
20
/ \
10 26
/ \ / \
4 18 24 27
/ \
14 19
/ \
13 15
Levelorder traversal of given tree is:
20, 10, 26, 4, 18, 24, 27, 14, 19, 13, 15
Input : 24
Output : 27
Input : 4
Output : 18
Enfoque :
- Compruebe si la raíz es NULL, es decir, el árbol está vacío. Si es verdadero, devuelve NULL.
- Compruebe si el Node dado es raíz. Si es verdad:
- Compruebe si existe el hijo izquierdo de la raíz, si es verdadero, devuelva el hijo izquierdo de la raíz.
- De lo contrario, verifique si existe el niño correcto, devuélvalo.
- Si la raíz es el único Node. Devuelve NULL.
- De lo contrario, realice el cruce de orden de nivel en el árbol utilizando una cola.
- En cada paso del recorrido del orden de nivel, verifique si el Node actual coincide con el Node dado.
- Si es Verdadero, deje de atravesar más y devuelva el elemento en la parte superior de la cola, que será el siguiente Node en el recorrido de orden de nivel.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find Levelorder
// successor of given node in the
// Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Tree Node
struct Node {
struct Node *left, *right;
int value;
};
// Utility function to create a
// new node with given value
struct Node* newNode(int value)
{
Node* temp = new Node;
temp->left = temp->right = NULL;
temp->value = value;
return temp;
}
// Function to find the Level Order Successor
// of a given Node in Binary Tree
Node* levelOrderSuccessor(Node* root, Node* key)
{
// Base Case
if (root == NULL)
return NULL;
// If root equals to key
if (root == key) {
// If left child exists it will be
// the Postorder Successor
if (root->left)
return root->left;
// Else if right child exists it will be
// the Postorder Successor
else if (root->right)
return root->right;
else
return NULL; // No Successor
}
// Create an empty queue for level
// order traversal
queue<Node*> q;
// Enqueue Root
q.push(root);
while (!q.empty()) {
Node* nd = q.front();
q.pop();
if (nd->left != NULL) {
q.push(nd->left);
}
if (nd->right != NULL) {
q.push(nd->right);
}
if (nd == key)
break;
}
return q.front();
}
// Driver code
int main()
{
struct Node* root = newNode(20);
root->left = newNode(10);
root->left->left = newNode(4);
root->left->right = newNode(18);
root->right = newNode(26);
root->right->left = newNode(24);
root->right->right = newNode(27);
root->left->right->left = newNode(14);
root->left->right->left->left = newNode(13);
root->left->right->left->right = newNode(15);
root->left->right->right = newNode(19);
struct Node* key = root->right->left; // node 24
struct Node* res = levelOrderSuccessor(root, key);
if (res)
cout << "LevelOrder successor of "
<< key->value << " is " << res->value;
else
cout << "LevelOrder successor of "
<< key->value << " is " << "NULL";
return 0;
}
Java
// Java program to find Levelorder
// successor of given node in the
// Binary Tree
import java.util.*;
class GfG {
// Tree Node
static class Node {
Node left, right;
int value;
}
// Utility function to create a
// new node with given value
static Node newNode(int value)
{
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.value = value;
return temp;
}
// Function to find the Level Order Successor
// of a given Node in Binary Tree
static Node levelOrderSuccessor(Node root, Node key)
{
// Base Case
if (root == null)
return null;
// If root equals to key
if (root == key) {
// If left child exists it will be
// the Postorder Successor
if (root.left != null)
return root.left;
// Else if right child exists it will be
// the Postorder Successor
else if (root.right != null)
return root.right;
else
return null; // No Successor
}
// Create an empty queue for level
// order traversal
Queue<Node> q = new LinkedList<Node> ();
// Enqueue Root
q.add(root);
while (!q.isEmpty()) {
Node nd = q.peek();
q.remove();
if (nd.left != null) {
q.add(nd.left);
}
if (nd.right != null) {
q.add(nd.right);
}
if (nd == key)
break;
}
return q.peek();
}
// Driver code
public static void main(String[] args)
{
Node root = newNode(20);
root.left = newNode(10);
root.left.left = newNode(4);
root.left.right = newNode(18);
root.right = newNode(26);
root.right.left = newNode(24);
root.right.right = newNode(27);
root.left.right.left = newNode(14);
root.left.right.left.left = newNode(13);
root.left.right.left.right = newNode(15);
root.left.right.right = newNode(19);
Node key = root.right.left; // node 24
Node res = levelOrderSuccessor(root, key);
if (res != null)
System.out.println("LevelOrder successor of "
+key.value + " is " + res.value);
else
System.out.println("LevelOrder successor of "
+key.value + " is NULL");
}
}
Python3
# Python3 program to find Level
# order successor of given node
# in the Binary Tree
# Node definition
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
# Function to find the Level
# Order Successor of a given
# Node in Binary Tree
def levelOrderSuccessor(root, key):
# Base Case
if root == None:
return None
# If root equals to key
elif root == key:
# If left child exists, it will
# be the PostOrder Successor
if root.left:
return root.left
# Else if right child exists, it
# will be the PostOrder Successor
elif root.right:
return root.right
# No Successor
else:
return None
# Create an empty queue for
# level order traversal
q = []
# Enqueue Root
q.append(root)
while len(q) != 0:
nd = q.pop(0)
if nd.left != None:
q.append(nd.left)
if nd.right != None:
q.append(nd.right)
if nd == key:
break
return q[0]
# Driver Code
if __name__ == "__main__":
root = Node(20)
root.left = Node(10)
root.left.left = Node(4)
root.left.right = Node(18)
root.right = Node(26)
root.right.left = Node(24)
root.right.right = Node(27)
root.left.right.left = Node(14)
root.left.right.left.left = Node(13)
root.left.right.left.right = Node(15)
root.left.right.right = Node(19)
key = root.right.left # node 24
res = levelOrderSuccessor(root, key)
if res:
print("LevelOrder successor of " +
str(key.value) + " is " +
str(res.value))
else:
print("LevelOrder successor of " +
str(key.value) + " is NULL")
# This code is contributed
# by Rituraj Jain
C#
// C# program to find Levelorder
// successor of given node in the
// Binary Tree
using System;
using System.Collections.Generic;
class GfG
{
// Tree Node
public class Node
{
public Node left, right;
public int value;
}
// Utility function to create a
// new node with given value
static Node newNode(int value)
{
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.value = value;
return temp;
}
// Function to find the Level Order Successor
// of a given Node in Binary Tree
static Node levelOrderSuccessor(Node root, Node key)
{
// Base Case
if (root == null)
return null;
// If root equals to key
if (root == key)
{
// If left child exists it will be
// the Postorder Successor
if (root.left != null)
return root.left;
// Else if right child exists it will be
// the Postorder Successor
else if (root.right != null)
return root.right;
else
return null; // No Successor
}
// Create an empty queue for level
// order traversal
LinkedList<Node> q = new LinkedList<Node> ();
// Enqueue Root
q.AddLast(root);
while (q.Count != 0)
{
Node nd = q.First.Value;
q.RemoveFirst();
if (nd.left != null)
{
q.AddLast(nd.left);
}
if (nd.right != null)
{
q.AddLast(nd.right);
}
if (nd == key)
break;
}
return q.First.Value;
}
// Driver code
public static void Main(String[] args)
{
Node root = newNode(20);
root.left = newNode(10);
root.left.left = newNode(4);
root.left.right = newNode(18);
root.right = newNode(26);
root.right.left = newNode(24);
root.right.right = newNode(27);
root.left.right.left = newNode(14);
root.left.right.left.left = newNode(13);
root.left.right.left.right = newNode(15);
root.left.right.right = newNode(19);
Node key = root.right.left; // node 24
Node res = levelOrderSuccessor(root, key);
if (res != null)
Console.WriteLine("LevelOrder successor of "
+key.value + " is " + res.value);
else
Console.WriteLine("LevelOrder successor of "
+key.value + " is NULL");
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find Levelorder
// successor of given node in the
// Binary Tree
// Tree Node
class Node
{
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
// Utility function to create a
// new node with given value
function newNode(value)
{
let temp = new Node(value);
return temp;
}
// Function to find the Level Order Successor
// of a given Node in Binary Tree
function levelOrderSuccessor(root, key)
{
// Base Case
if (root == null)
return null;
// If root equals to key
if (root == key) {
// If left child exists it will be
// the Postorder Successor
if (root.left != null)
return root.left;
// Else if right child exists it will be
// the Postorder Successor
else if (root.right != null)
return root.right;
else
return null; // No Successor
}
// Create an empty queue for level
// order traversal
let q = [];
// Enqueue Root
q.push(root);
while (q.length > 0) {
let nd = q[0];
q.shift();
if (nd.left != null) {
q.push(nd.left);
}
if (nd.right != null) {
q.push(nd.right);
}
if (nd == key)
break;
}
return q[0];
}
let root = newNode(20);
root.left = newNode(10);
root.left.left = newNode(4);
root.left.right = newNode(18);
root.right = newNode(26);
root.right.left = newNode(24);
root.right.right = newNode(27);
root.left.right.left = newNode(14);
root.left.right.left.left = newNode(13);
root.left.right.left.right = newNode(15);
root.left.right.right = newNode(19);
let key = root.right.left; // node 24
let res = levelOrderSuccessor(root, key);
if (res != null)
document.write("LevelOrder successor of "
+key.value + " is " + res.value);
else
document.write("LevelOrder successor of "
+key.value + " is NULL");
</script>
Producción:
LevelOrder successor of 24 is 27
Complejidad de tiempo : O (N), ya que estamos usando un ciclo while que atravesará N veces, donde N es el número de Nodes en el árbol.
Espacio auxiliar : O (N), ya que estamos usando espacio adicional para la cola, que estamos usando para el recorrido de orden de nivel.