Dado un árbol binario y un Node en el árbol binario, encuentre el sucesor de preorden del Node dado. Se puede suponer que cada Node tiene un enlace principal.
Ejemplos:
Consider the following binary tree
20
/ \
10 26
/ \ / \
4 18 24 27
/ \
14 19
/ \
13 15
Input : 4
Output : 18
Preorder traversal of given tree is 20, 10, 4,
18, 14, 13, 15, 19, 26, 24, 27.
Input : 19
Output : 26
Una solución simple es almacenar primero el recorrido Preorder del árbol dado en una array, luego buscar linealmente el Node dado e imprimir el Node al lado.
Complejidad Temporal: O(n), ya que recorreremos el árbol para buscar el Node.
Espacio Auxiliar: O(n), ya que necesitamos espacio extra para almacenar los elementos del árbol.
Una solución eficiente se basa en las siguientes observaciones.
- Si el hijo izquierdo de un Node dado existe, entonces el hijo izquierdo es el sucesor de preorden.
- Sin embargo, si el hijo izquierdo no existe, el hijo derecho existe, entonces el sucesor del pedido previo es el hijo derecho.
- Si el hijo izquierdo y el hijo derecho no existen y el Node dado es el hijo izquierdo de su padre, entonces su hermano es su sucesor de preorden.
- Si no se cumple ninguna de las condiciones anteriores (el hijo izquierdo no existe y el Node dado no es hijo izquierdo de su padre), entonces avanzamos usando punteros de padres hasta que ocurra uno de los siguientes.
- Llegamos a la raíz. En este caso, no existe un sucesor de pedido anticipado.
- El Node actual (uno de los ancestros del Node dado) es el hijo izquierdo de su padre, en este caso, el sucesor de preorden es un hermano del Node actual.
C++
// CPP program to find preorder successor of
// a node in Binary Tree.
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preorderSuccessor(Node* root, Node* n)
{
// If left child exists, then it is preorder
// successor.
if (n->left)
return n->left;
// If left child does not exist and right child
// exists, then it is preorder successor.
if (n->right)
return n->right;
// If left child does not exist, then
// travel up (using parent pointers)
// until we reach a node which is left
// child of its parent.
Node *curr = n, *parent = curr->parent;
while (parent != NULL && parent->right == curr) {
curr = curr->parent;
parent = parent->parent;
}
// If we reached root, then the given
// node has no preorder successor
if (parent == NULL)
return NULL;
return parent->right;
}
int main()
{
Node* root = newNode(20);
root->parent = NULL;
root->left = newNode(10);
root->left->parent = root;
root->left->left = newNode(4);
root->left->left->parent = root->left;
root->left->right = newNode(18);
root->left->right->parent = root->left;
root->right = newNode(26);
root->right->parent = root;
root->right->left = newNode(24);
root->right->left->parent = root->right;
root->right->right = newNode(27);
root->right->right->parent = root->right;
root->left->right->left = newNode(14);
root->left->right->left->parent = root->left->right;
root->left->right->left->left = newNode(13);
root->left->right->left->left->parent = root->left->right->left;
root->left->right->left->right = newNode(15);
root->left->right->left->right->parent = root->left->right->left;
root->left->right->right = newNode(19);
root->left->right->right->parent = root->left->right;
Node* res = preorderSuccessor(root, root->left->right->right);
if (res) {
printf("Preorder successor of %d is %d\n",
root->left->right->right->key, res->key);
}
else {
printf("Preorder successor of %d is NULL\n",
root->left->right->right->key);
}
return 0;
}
Java
// Java program to find preorder successor of
// a node in Binary Tree.
class Solution
{
static class Node
{
Node left, right, parent;
int key;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.left = temp.right = temp.parent = null;
temp.key = key;
return temp;
}
static Node preorderSuccessor(Node root, Node n)
{
// If left child exists, then it is preorder
// successor.
if (n.left != null)
return n.left;
// If left child does not exist and right child
// exists, then it is preorder successor.
if (n.right != null)
return n.right;
// If left child does not exist, then
// travel up (using parent pointers)
// until we reach a node which is left
// child of its parent.
Node curr = n, parent = curr.parent;
while (parent != null && parent.right == curr)
{
curr = curr.parent;
parent = parent.parent;
}
// If we reached root, then the given
// node has no preorder successor
if (parent == null)
return null;
return parent.right;
}
// Driver code
public static void main(String args[])
{
Node root = newNode(20);
root.parent = null;
root.left = newNode(10);
root.left.parent = root;
root.left.left = newNode(4);
root.left.left.parent = root.left;
root.left.right = newNode(18);
root.left.right.parent = root.left;
root.right = newNode(26);
root.right.parent = root;
root.right.left = newNode(24);
root.right.left.parent = root.right;
root.right.right = newNode(27);
root.right.right.parent = root.right;
root.left.right.left = newNode(14);
root.left.right.left.parent = root.left.right;
root.left.right.left.left = newNode(13);
root.left.right.left.left.parent = root.left.right.left;
root.left.right.left.right = newNode(15);
root.left.right.left.right.parent = root.left.right.left;
root.left.right.right = newNode(19);
root.left.right.right.parent = root.left.right;
Node res = preorderSuccessor(root, root.left.right.right);
if (res != null)
{
System.out.printf("Preorder successor of %d is %d\n",
root.left.right.right.key, res.key);
}
else
{
System.out.printf("Preorder successor of %d is null\n",
root.left.right.right.key);
}
}
}
// This code is contributed by Arnab Kundu
Python3
""" Python3 program to find preorder
successor of a node in Binary Tree."""
# A Binary Tree Node
# Utility function to create a new tree node
class newNode:
# Constructor to create a new node
def __init__(self, data):
self.key = data
self.left = None
self.right = None
self.parent = None
def preorderSuccessor(root, n):
# If left child exists, then it is
# preorder successor.
if (n.left):
return n.left
# If left child does not exist and right child
# exists, then it is preorder successor.
if (n.right):
return n.right
# If left child does not exist, then
# travel up (using parent pointers)
# until we reach a node which is left
# child of its parent.
curr = n
parent = curr.parent
while (parent != None and
parent.right == curr):
curr = curr.parent
parent = parent.parent
# If we reached root, then the given
# node has no preorder successor
if (parent == None):
return None
return parent.right
# Driver Code
if __name__ == '__main__':
root = newNode(20)
root.parent = None
root.left = newNode(10)
root.left.parent = root
root.left.left = newNode(4)
root.left.left.parent = root.left
root.left.right = newNode(18)
root.left.right.parent = root.left
root.right = newNode(26)
root.right.parent = root
root.right.left = newNode(24)
root.right.left.parent = root.right
root.right.right = newNode(27)
root.right.right.parent = root.right
root.left.right.left = newNode(14)
root.left.right.left.parent = root.left.right
root.left.right.left.left = newNode(13)
root.left.right.left.left.parent = root.left.right.left
root.left.right.left.right = newNode(15)
root.left.right.left.right.parent = root.left.right.left
root.left.right.right = newNode(19)
root.left.right.right.parent = root.left.right
res = preorderSuccessor(root, root.left.right.right)
if (res):
print("Preorder successor of",
root.left.right.right.key, "is", res.key)
else:
print("Preorder successor of",
root.left.right.right.key, "is None")
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to find preorder successor of
// a node in Binary Tree.
using System;
class GFG
{
public class Node
{
public Node left, right, parent;
public int key;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.left = temp.right = temp.parent = null;
temp.key = key;
return temp;
}
static Node preorderSuccessor(Node root, Node n)
{
// If left child exists, then it is preorder
// successor.
if (n.left != null)
return n.left;
// If left child does not exist and right child
// exists, then it is preorder successor.
if (n.right != null)
return n.right;
// If left child does not exist, then
// travel up (using parent pointers)
// until we reach a node which is left
// child of its parent.
Node curr = n, parent = curr.parent;
while (parent != null && parent.right == curr)
{
curr = curr.parent;
parent = parent.parent;
}
// If we reached root, then the given
// node has no preorder successor
if (parent == null)
return null;
return parent.right;
}
// Driver code
public static void Main(String []args)
{
Node root = newNode(20);
root.parent = null;
root.left = newNode(10);
root.left.parent = root;
root.left.left = newNode(4);
root.left.left.parent = root.left;
root.left.right = newNode(18);
root.left.right.parent = root.left;
root.right = newNode(26);
root.right.parent = root;
root.right.left = newNode(24);
root.right.left.parent = root.right;
root.right.right = newNode(27);
root.right.right.parent = root.right;
root.left.right.left = newNode(14);
root.left.right.left.parent = root.left.right;
root.left.right.left.left = newNode(13);
root.left.right.left.left.parent = root.left.right.left;
root.left.right.left.right = newNode(15);
root.left.right.left.right.parent = root.left.right.left;
root.left.right.right = newNode(19);
root.left.right.right.parent = root.left.right;
Node res = preorderSuccessor(root, root.left.right.right);
if (res != null)
{
Console.Write("Preorder successor of {0} is {1}\n",
root.left.right.right.key, res.key);
}
else
{
Console.Write("Preorder successor of {0} is null\n",
root.left.right.right.key);
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find preorder successor of
// a node in Binary Tree.
class Node
{
constructor(key)
{
this.key=key;
this.left=this.right=this.parent=null;
}
}
function preorderSuccessor(root,n)
{
// If left child exists, then it is preorder
// successor.
if (n.left != null)
return n.left;
// If left child does not exist and right child
// exists, then it is preorder successor.
if (n.right != null)
return n.right;
// If left child does not exist, then
// travel up (using parent pointers)
// until we reach a node which is left
// child of its parent.
let curr = n, parent = curr.parent;
while (parent != null && parent.right == curr)
{
curr = curr.parent;
parent = parent.parent;
}
// If we reached root, then the given
// node has no preorder successor
if (parent == null)
return null;
return parent.right;
}
// Driver code
let root = new Node(20);
root.parent = null;
root.left = new Node(10);
root.left.parent = root;
root.left.left = new Node(4);
root.left.left.parent = root.left;
root.left.right = new Node(18);
root.left.right.parent = root.left;
root.right = new Node(26);
root.right.parent = root;
root.right.left = new Node(24);
root.right.left.parent = root.right;
root.right.right = new Node(27);
root.right.right.parent = root.right;
root.left.right.left = new Node(14);
root.left.right.left.parent = root.left.right;
root.left.right.left.left = new Node(13);
root.left.right.left.left.parent = root.left.right.left;
root.left.right.left.right = new Node(15);
root.left.right.left.right.parent = root.left.right.left;
root.left.right.right = new Node(19);
root.left.right.right.parent = root.left.right;
let res = preorderSuccessor(root, root.left.right.right);
if (res != null)
{
document.write("Preorder successor of "+
root.left.right.right.key+" is "+res.key+"<br>");
}
else
{
System.out.printf("Preorder successor of "+
root.left.right.right.key+" is null<br>");
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Preorder successor of 19 is 26
Complejidad de tiempo: O(h) donde h es la altura del árbol binario dado, ya que no estamos atravesando todos los Nodes. Hemos comprobado el hijo de cada Node que es equivalente a atravesar la altura del árbol.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por NayanGadre y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA