Dado un árbol binario, la tarea es encontrar y ELIMINAR el último Node hoja.
El Node hoja es un Node sin hijos. El último Node de hoja sería el último Node que se recorre en secuencia durante el cruce de orden de nivel . El enunciado del problema es identificar este último Node visitado y eliminar este Node en particular.
Ejemplos:
Input:
Given Tree is:
6
/ \
5 4
/ \ \
1 2 5
Level Order Traversal is: 6 5 4 1 2 5
Output:
After deleting the last node (5),
the tree would look like as follows.
6
/ \
5 4
/ \
1 2
Level Order Traversal is: 6 5 4 1 2
Input:
Given tree is:
1
/ \
3 10
/ \ / \
2 15 4 5
/
1
Level Order Traversal is: 1 3 10 2 15 4 5 1
Output:
After deleting the last node (1),
the tree would look like as follows.
1
/ \
3 10
/ \ / \
2 15 4 5
Level Order Traversal is: 1 3 10 2 15 4 5
Este problema es ligeramente diferente de Eliminar Node de hoja con valor como X , en el que se nos proporciona de inmediato el valor del último Node de hoja (X) que se eliminará, en función del cual realizamos comprobaciones y marcamos el Node principal como nulo para eliminarlo.
Este enfoque identificaría el último Node hoja presente en el último nivel del árbol y lo eliminaría.
Enfoque 1: Atravesar Nodes de último nivel y realizar un seguimiento del padre y el Node atravesado.
Este enfoque atravesaría cada Node hasta llegar al último nivel del árbol binario dado. Durante el recorrido, hacemos un seguimiento del último Node recorrido y su padre.
Una vez que haya terminado con el recorrido, verifique si el padre tiene Right Child, si es así, configúrelo en NULL. Si no, establezca el puntero izquierdo en NULL
A continuación se muestra la implementación del enfoque:
C++
// CPP implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Tree Node
class Node
{
public:
int data;
Node *left, *right;
Node(int data) : data(data) {}
};
// Method to perform inorder traversal
void inorder(Node *root)
{
if (root == NULL)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
// To keep track of last processed
// nodes parent and node itself.
Node *lastNode, *parentOfLastNode;
// Method to get the height of the tree
int height(Node *root)
{
if (root == NULL)
return 0;
int lheight = height(root->left) + 1;
int rheight = height(root->right) + 1;
return max(lheight, rheight);
}
// Method to keep track of parents
// of every node
void getLastNodeAndItsParent(Node *root, int level, Node *parent)
{
if (root == NULL)
return;
// The last processed node in
// Level Order Traversal has to
// be the node to be deleted.
// This will store the last
// processed node and its parent.
if (level == 1)
{
lastNode = root;
parentOfLastNode = parent;
}
getLastNodeAndItsParent(root->left, level - 1, root);
getLastNodeAndItsParent(root->right, level - 1, root);
}
// Method to delete last leaf node
void deleteLastNode(Node *root)
{
int levelOfLastNode = height(root);
getLastNodeAndItsParent(root, levelOfLastNode, NULL);
if (lastNode and parentOfLastNode)
{
if (parentOfLastNode->right)
parentOfLastNode->right = NULL;
else
parentOfLastNode->left = NULL;
}
else
cout << "Empty Tree\n";
}
// Driver Code
int main()
{
Node *root = new Node(6);
root->left = new Node(5);
root->right = new Node(4);
root->left->left = new Node(1);
root->left->right = new Node(2);
root->right->right = new Node(5);
cout << "Inorder traversal before deletion of last node :\n";
inorder(root);
deleteLastNode(root);
cout << "\nInorder traversal after deletion of last node :\n";
inorder(root);
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java Implementation of the approach
public class DeleteLastNode {
// Tree Node
static class Node {
Node left, right;
int data;
Node(int data)
{
this.data = data;
}
}
// Method to perform inorder traversal
public void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// To keep track of last processed
// nodes parent and node itself.
public static Node lastNode;
public static Node parentOfLastNode;
// Method to get the height of the tree
public int height(Node root)
{
if (root == null)
return 0;
int lheight = height(root.left) + 1;
int rheight = height(root.right) + 1;
return Math.max(lheight, rheight);
}
// Method to delete last leaf node
public void deleteLastNode(Node root)
{
int levelOfLastNode = height(root);
// Get all nodes at last level
getLastNodeAndItsParent(root,
levelOfLastNode,
null);
if (lastNode != null
&& parentOfLastNode != null) {
if (parentOfLastNode.right != null)
parentOfLastNode.right = null;
else
parentOfLastNode.left = null;
}
else
System.out.println("Empty Tree");
}
// Method to keep track of parents
// of every node
public void getLastNodeAndItsParent(Node root,
int level,
Node parent)
{
if (root == null)
return;
// The last processed node in
// Level Order Traversal has to
// be the node to be deleted.
// This will store the last
// processed node and its parent.
if (level == 1) {
lastNode = root;
parentOfLastNode = parent;
}
getLastNodeAndItsParent(root.left,
level - 1,
root);
getLastNodeAndItsParent(root.right,
level - 1,
root);
}
// Driver Code
public static void main(String[] args)
{
Node root = new Node(6);
root.left = new Node(5);
root.right = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(2);
root.right.right = new Node(5);
DeleteLastNode deleteLastNode = new DeleteLastNode();
System.out.println("Inorder traversal "
+ "before deletion "
+ "of last node : ");
deleteLastNode.inorder(root);
deleteLastNode.deleteLastNode(root);
System.out.println("\nInorder traversal "
+ "after deletion of "
+ "last node : ");
deleteLastNode.inorder(root);
}
}
C#
// C# implementation of the above approach
using System;
class GFG
{
// Tree Node
public class Node
{
public Node left, right;
public int data;
public Node(int data)
{
this.data = data;
}
}
// Method to perform inorder traversal
public void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
Console.Write(root.data + " ");
inorder(root.right);
}
// To keep track of last processed
// nodes parent and node itself.
public static Node lastNode;
public static Node parentOfLastNode;
// Method to get the height of the tree
public int height(Node root)
{
if (root == null)
return 0;
int lheight = height(root.left) + 1;
int rheight = height(root.right) + 1;
return Math.Max(lheight, rheight);
}
// Method to delete last leaf node
public void deleteLastNode(Node root)
{
int levelOfLastNode = height(root);
// Get all nodes at last level
getLastNodeAndItsParent(root,
levelOfLastNode,
null);
if (lastNode != null &&
parentOfLastNode != null)
{
if (parentOfLastNode.right != null)
parentOfLastNode.right = null;
else
parentOfLastNode.left = null;
}
else
Console.WriteLine("Empty Tree");
}
// Method to keep track of parents
// of every node
public void getLastNodeAndItsParent(Node root,
int level,
Node parent)
{
if (root == null)
return;
// The last processed node in
// Level Order Traversal has to
// be the node to be deleted.
// This will store the last
// processed node and its parent.
if (level == 1)
{
lastNode = root;
parentOfLastNode = parent;
}
getLastNodeAndItsParent(root.left,
level - 1,
root);
getLastNodeAndItsParent(root.right,
level - 1,
root);
}
// Driver Code
public static void Main(String[] args)
{
Node root = new Node(6);
root.left = new Node(5);
root.right = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(2);
root.right.right = new Node(5);
GFG deleteLastNode = new GFG();
Console.WriteLine("Inorder traversal " +
"before deletion " +
"of last node : ");
deleteLastNode.inorder(root);
deleteLastNode.deleteLastNode(root);
Console.WriteLine("\nInorder traversal " +
"after deletion of " +
"last node : ");
deleteLastNode.inorder(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach
// Tree Node
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Method to perform inorder traversal
function inorder(root)
{
if (root == null)
return;
inorder(root.left);
document.write(root.data + " ");
inorder(root.right);
}
// To keep track of last processed
// nodes parent and node itself.
var lastNode = null;
var parentOfLastNode = null;
// Method to get the height of the tree
function height(root)
{
if (root == null)
return 0;
var lheight = height(root.left) + 1;
var rheight = height(root.right) + 1;
return Math.max(lheight, rheight);
}
// Method to delete last leaf node
function deleteLastNode(root)
{
var levelOfLastNode = height(root);
// Get all nodes at last level
getLastNodeAndItsParent(root,
levelOfLastNode,
null);
if (lastNode != null &&
parentOfLastNode != null)
{
if (parentOfLastNode.right != null)
parentOfLastNode.right = null;
else
parentOfLastNode.left = null;
}
else
Console.WriteLine("Empty Tree");
}
// Method to keep track of parents
// of every node
function getLastNodeAndItsParent(root, level, parent)
{
if (root == null)
return;
// The last processed node in
// Level Order Traversal has to
// be the node to be deleted.
// This will store the last
// processed node and its parent.
if (level == 1)
{
lastNode = root;
parentOfLastNode = parent;
}
getLastNodeAndItsParent(root.left,
level - 1,
root);
getLastNodeAndItsParent(root.right,
level - 1,
root);
}
// Driver Code
var root = new Node(6);
root.left = new Node(5);
root.right = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(2);
root.right.right = new Node(5);
document.write("Inorder traversal " +
"before deletion " +
"of last node :<br>");
inorder(root);
deleteLastNode(root);
document.write("<br>Inorder traversal " +
"after deletion of " +
"last node :<br>");
inorder(root);
// This code is contributed by rrrtnx.
</script>
Producción:
Inorder traversal before deletion of last node : 1 5 2 6 4 5 Inorder traversal after deletion of last node : 1 5 2 6 4
Complejidad del tiempo: 
dado que cada Node se atravesaría una vez, el tiempo necesario sería lineal con respecto al número de Nodes en un árbol determinado.
Enfoque 2: Realización de un cruce de orden de niveles en un árbol binario determinado mediante la cola y el seguimiento del padre y el último Node recorrido.
Esta es una forma no recursiva de lograr el enfoque anterior 1. Realizamos el cruce de orden de nivel utilizando la cola y realizando un seguimiento de cada Node visitado y su padre. El último Node visitado sería el último Node que se eliminará.
A continuación se muestra la implementación del enfoque:
Java
// Java implementation
import java.util.LinkedList;
import java.util.Queue;
public class DeleteLastNode {
// Tree Node
static class Node {
Node left, right;
int data;
Node(int data)
{
this.data = data;
}
}
// Function to perform the inorder traversal of the tree
public void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// To keep track of last
// processed nodes parent
// and node itself.
public static Node lastLevelLevelOrder;
public static Node parentOfLastNode;
// Method to delete the last node
// from the tree
public void deleteLastNode(Node root)
{
// If tree is empty, it
// would return without
// any deletion
if (root == null)
return;
// The queue would be needed
// to maintain the level order
// traversal of nodes
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
// The traversing would
// continue until all
// nodes are traversed once
while (!queue.isEmpty()) {
Node temp = queue.poll();
// If there is left child
if (temp.left != null) {
queue.offer(temp.left);
// For every traversed node,
// we would check if it is a
// leaf node by checking if
// current node has children to it
if (temp.left.left == null
&& temp.left.right == null) {
// For every leaf node
// encountered, we would
// keep not of it as
// "Previously Visided Leaf node.
lastLevelLevelOrder = temp.left;
parentOfLastNode = temp;
}
}
if (temp.right != null) {
queue.offer(temp.right);
if (temp.right.left == null
&& temp.right.right == null) {
// For every leaf node
// encountered, we would
// keep not of it as
// "Previously Visided Leaf node.
lastLevelLevelOrder = temp.right;
parentOfLastNode = temp;
}
}
}
// Once out of above loop.
// we would certainly have
// last visited node, which
// is to be deleted and its
// parent node.
if (lastLevelLevelOrder != null
&& parentOfLastNode != null) {
// If last node is right child
// of parent, make right node
// of its parent as NULL or
// make left node as NULL
if (parentOfLastNode.right != null)
parentOfLastNode.right = null;
else
parentOfLastNode.left = null;
}
else
System.out.println("Empty Tree");
}
// Driver Code
public static void main(String[] args)
{
Node root = new Node(6);
root.left = new Node(5);
root.right = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(2);
root.right.right = new Node(5);
DeleteLastNode deleteLastNode
= new DeleteLastNode();
System.out.println("Inorder traversal "
+ "before deletion of "
+ "last node : ");
deleteLastNode.inorder(root);
deleteLastNode.deleteLastNode(root);
System.out.println("\nInorder traversal "
+ "after deletion "
+ "of last node : ");
deleteLastNode.inorder(root);
}
}
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
public class DeleteLastNode {
// Tree Node
public class Node {
public Node left, right;
public int data;
public Node(int data)
{
this.data = data;
}
}
// Function to perform the inorder traversal of the tree
public void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
Console.Write(root.data + " ");
inorder(root.right);
}
// To keep track of last
// processed nodes parent
// and node itself.
public static Node lastLevelLevelOrder;
public static Node parentOfLastNode;
// Method to delete the last node
// from the tree
public void deleteLastNode(Node root)
{
// If tree is empty, it
// would return without
// any deletion
if (root == null)
return;
// The queue would be needed
// to maintain the level order
// traversal of nodes
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
// The traversing would
// continue until all
// nodes are traversed once
while (queue.Count!=0) {
Node temp = queue.Dequeue();
// If there is left child
if (temp.left != null) {
queue.Enqueue(temp.left);
// For every traversed node,
// we would check if it is a
// leaf node by checking if
// current node has children to it
if (temp.left.left == null
&& temp.left.right == null) {
// For every leaf node
// encountered, we would
// keep not of it as
// "Previously Visided Leaf node.
lastLevelLevelOrder = temp.left;
parentOfLastNode = temp;
}
}
if (temp.right != null) {
queue.Enqueue(temp.right);
if (temp.right.left == null
&& temp.right.right == null) {
// For every leaf node
// encountered, we would
// keep not of it as
// "Previously Visided Leaf node.
lastLevelLevelOrder = temp.right;
parentOfLastNode = temp;
}
}
}
// Once out of above loop.
// we would certainly have
// last visited node, which
// is to be deleted and its
// parent node.
if (lastLevelLevelOrder != null
&& parentOfLastNode != null) {
// If last node is right child
// of parent, make right node
// of its parent as NULL or
// make left node as NULL
if (parentOfLastNode.right != null)
parentOfLastNode.right = null;
else
parentOfLastNode.left = null;
}
else
Console.WriteLine("Empty Tree");
}
// Driver Code
public static void Main(String[] args)
{
Node root = new Node(6);
root.left = new Node(5);
root.right = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(2);
root.right.right = new Node(5);
DeleteLastNode deleteLastNode
= new DeleteLastNode();
Console.WriteLine("Inorder traversal "
+ "before deletion of "
+ "last node : ");
deleteLastNode.inorder(root);
deleteLastNode.deleteLastNode(root);
Console.WriteLine("\nInorder traversal "
+ "after deletion "
+ "of last node : ");
deleteLastNode.inorder(root);
}
}
// This code contributed by Rajput-Ji
Producción:
Inorder traversal before deletion of last node : 1 5 2 6 4 5 Inorder traversal after deletion of last node : 1 5 2 6 4
Complejidad del tiempo:
dado que cada Node se visitaría una vez, el tiempo necesario sería lineal con respecto al número de Nodes presentes en el árbol.
Espacio Auxiliar:
Dado que estaríamos manteniendo una cola para hacer el recorrido de orden de niveles, el espacio consumido sería de .